1 //===- InstCombineInternal.h - InstCombine pass internals -------*- C++ -*-===//
3 // The LLVM Compiler Infrastructure
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
8 //===----------------------------------------------------------------------===//
11 /// This file provides internal interfaces used to implement the InstCombine.
13 //===----------------------------------------------------------------------===//
15 #ifndef LLVM_LIB_TRANSFORMS_INSTCOMBINE_INSTCOMBINEINTERNAL_H
16 #define LLVM_LIB_TRANSFORMS_INSTCOMBINE_INSTCOMBINEINTERNAL_H
18 #include "llvm/Analysis/AliasAnalysis.h"
19 #include "llvm/Analysis/AssumptionCache.h"
20 #include "llvm/Analysis/InstructionSimplify.h"
21 #include "llvm/Analysis/LoopInfo.h"
22 #include "llvm/Analysis/TargetFolder.h"
23 #include "llvm/Analysis/ValueTracking.h"
24 #include "llvm/IR/Dominators.h"
25 #include "llvm/IR/IRBuilder.h"
26 #include "llvm/IR/InstVisitor.h"
27 #include "llvm/IR/IntrinsicInst.h"
28 #include "llvm/IR/Operator.h"
29 #include "llvm/IR/PatternMatch.h"
30 #include "llvm/Pass.h"
31 #include "llvm/Support/KnownBits.h"
32 #include "llvm/Transforms/InstCombine/InstCombineWorklist.h"
33 #include "llvm/Transforms/Utils/Local.h"
35 #define DEBUG_TYPE "instcombine"
41 class TargetLibraryInfo;
46 /// Assign a complexity or rank value to LLVM Values. This is used to reduce
47 /// the amount of pattern matching needed for compares and commutative
48 /// instructions. For example, if we have:
49 /// icmp ugt X, Constant
51 /// xor (add X, Constant), cast Z
53 /// We do not have to consider the commuted variants of these patterns because
54 /// canonicalization based on complexity guarantees the above ordering.
56 /// This routine maps IR values to various complexity ranks:
59 /// 2 -> Other non-instructions
61 /// 4 -> Cast and (f)neg/not instructions
62 /// 5 -> Other instructions
63 static inline unsigned getComplexity(Value *V) {
64 if (isa<Instruction>(V)) {
65 if (isa<CastInst>(V) || BinaryOperator::isNeg(V) ||
66 BinaryOperator::isFNeg(V) || BinaryOperator::isNot(V))
72 return isa<Constant>(V) ? (isa<UndefValue>(V) ? 0 : 1) : 2;
75 /// Predicate canonicalization reduces the number of patterns that need to be
76 /// matched by other transforms. For example, we may swap the operands of a
77 /// conditional branch or select to create a compare with a canonical (inverted)
78 /// predicate which is then more likely to be matched with other values.
79 static inline bool isCanonicalPredicate(CmpInst::Predicate Pred) {
81 case CmpInst::ICMP_NE:
82 case CmpInst::ICMP_ULE:
83 case CmpInst::ICMP_SLE:
84 case CmpInst::ICMP_UGE:
85 case CmpInst::ICMP_SGE:
86 // TODO: There are 16 FCMP predicates. Should others be (not) canonical?
87 case CmpInst::FCMP_ONE:
88 case CmpInst::FCMP_OLE:
89 case CmpInst::FCMP_OGE:
96 /// Return the source operand of a potentially bitcasted value while optionally
97 /// checking if it has one use. If there is no bitcast or the one use check is
98 /// not met, return the input value itself.
99 static inline Value *peekThroughBitcast(Value *V, bool OneUseOnly = false) {
100 if (auto *BitCast = dyn_cast<BitCastInst>(V))
101 if (!OneUseOnly || BitCast->hasOneUse())
102 return BitCast->getOperand(0);
104 // V is not a bitcast or V has more than one use and OneUseOnly is true.
108 /// \brief Add one to a Constant
109 static inline Constant *AddOne(Constant *C) {
110 return ConstantExpr::getAdd(C, ConstantInt::get(C->getType(), 1));
112 /// \brief Subtract one from a Constant
113 static inline Constant *SubOne(Constant *C) {
114 return ConstantExpr::getSub(C, ConstantInt::get(C->getType(), 1));
117 /// \brief Return true if the specified value is free to invert (apply ~ to).
118 /// This happens in cases where the ~ can be eliminated. If WillInvertAllUses
119 /// is true, work under the assumption that the caller intends to remove all
120 /// uses of V and only keep uses of ~V.
122 static inline bool IsFreeToInvert(Value *V, bool WillInvertAllUses) {
124 if (BinaryOperator::isNot(V))
127 // Constants can be considered to be not'ed values.
128 if (isa<ConstantInt>(V))
131 // A vector of constant integers can be inverted easily.
132 if (V->getType()->isVectorTy() && isa<Constant>(V)) {
133 unsigned NumElts = V->getType()->getVectorNumElements();
134 for (unsigned i = 0; i != NumElts; ++i) {
135 Constant *Elt = cast<Constant>(V)->getAggregateElement(i);
139 if (isa<UndefValue>(Elt))
142 if (!isa<ConstantInt>(Elt))
148 // Compares can be inverted if all of their uses are being modified to use the
151 return WillInvertAllUses;
153 // If `V` is of the form `A + Constant` then `-1 - V` can be folded into `(-1
154 // - Constant) - A` if we are willing to invert all of the uses.
155 if (BinaryOperator *BO = dyn_cast<BinaryOperator>(V))
156 if (BO->getOpcode() == Instruction::Add ||
157 BO->getOpcode() == Instruction::Sub)
158 if (isa<Constant>(BO->getOperand(0)) || isa<Constant>(BO->getOperand(1)))
159 return WillInvertAllUses;
165 /// \brief Specific patterns of overflow check idioms that we match.
166 enum OverflowCheckFlavor {
177 /// \brief Returns the OverflowCheckFlavor corresponding to a overflow_with_op
179 static inline OverflowCheckFlavor
180 IntrinsicIDToOverflowCheckFlavor(unsigned ID) {
184 case Intrinsic::uadd_with_overflow:
185 return OCF_UNSIGNED_ADD;
186 case Intrinsic::sadd_with_overflow:
187 return OCF_SIGNED_ADD;
188 case Intrinsic::usub_with_overflow:
189 return OCF_UNSIGNED_SUB;
190 case Intrinsic::ssub_with_overflow:
191 return OCF_SIGNED_SUB;
192 case Intrinsic::umul_with_overflow:
193 return OCF_UNSIGNED_MUL;
194 case Intrinsic::smul_with_overflow:
195 return OCF_SIGNED_MUL;
199 /// \brief The core instruction combiner logic.
201 /// This class provides both the logic to recursively visit instructions and
203 class LLVM_LIBRARY_VISIBILITY InstCombiner
204 : public InstVisitor<InstCombiner, Instruction *> {
205 // FIXME: These members shouldn't be public.
207 /// \brief A worklist of the instructions that need to be simplified.
208 InstCombineWorklist &Worklist;
210 /// \brief An IRBuilder that automatically inserts new instructions into the
212 typedef IRBuilder<TargetFolder, IRBuilderCallbackInserter> BuilderTy;
216 // Mode in which we are running the combiner.
217 const bool MinimizeSize;
218 /// Enable combines that trigger rarely but are costly in compiletime.
219 const bool ExpensiveCombines;
223 // Required analyses.
225 TargetLibraryInfo &TLI;
227 const DataLayout &DL;
228 const SimplifyQuery SQ;
229 // Optional analyses. When non-null, these can both be used to do better
230 // combining and will be updated to reflect any changes.
236 InstCombiner(InstCombineWorklist &Worklist, BuilderTy &Builder,
237 bool MinimizeSize, bool ExpensiveCombines, AliasAnalysis *AA,
238 AssumptionCache &AC, TargetLibraryInfo &TLI, DominatorTree &DT,
239 const DataLayout &DL, LoopInfo *LI)
240 : Worklist(Worklist), Builder(Builder), MinimizeSize(MinimizeSize),
241 ExpensiveCombines(ExpensiveCombines), AA(AA), AC(AC), TLI(TLI), DT(DT),
242 DL(DL), SQ(DL, &TLI, &DT, &AC), LI(LI), MadeIRChange(false) {}
244 /// \brief Run the combiner over the entire worklist until it is empty.
246 /// \returns true if the IR is changed.
249 AssumptionCache &getAssumptionCache() const { return AC; }
251 const DataLayout &getDataLayout() const { return DL; }
253 DominatorTree &getDominatorTree() const { return DT; }
255 LoopInfo *getLoopInfo() const { return LI; }
257 TargetLibraryInfo &getTargetLibraryInfo() const { return TLI; }
259 // Visitation implementation - Implement instruction combining for different
260 // instruction types. The semantics are as follows:
262 // null - No change was made
263 // I - Change was made, I is still valid, I may be dead though
264 // otherwise - Change was made, replace I with returned instruction
266 Instruction *visitAdd(BinaryOperator &I);
267 Instruction *visitFAdd(BinaryOperator &I);
268 Value *OptimizePointerDifference(Value *LHS, Value *RHS, Type *Ty);
269 Instruction *visitSub(BinaryOperator &I);
270 Instruction *visitFSub(BinaryOperator &I);
271 Instruction *visitMul(BinaryOperator &I);
272 Value *foldFMulConst(Instruction *FMulOrDiv, Constant *C,
273 Instruction *InsertBefore);
274 Instruction *visitFMul(BinaryOperator &I);
275 Instruction *visitURem(BinaryOperator &I);
276 Instruction *visitSRem(BinaryOperator &I);
277 Instruction *visitFRem(BinaryOperator &I);
278 bool SimplifyDivRemOfSelect(BinaryOperator &I);
279 Instruction *commonRemTransforms(BinaryOperator &I);
280 Instruction *commonIRemTransforms(BinaryOperator &I);
281 Instruction *commonDivTransforms(BinaryOperator &I);
282 Instruction *commonIDivTransforms(BinaryOperator &I);
283 Instruction *visitUDiv(BinaryOperator &I);
284 Instruction *visitSDiv(BinaryOperator &I);
285 Instruction *visitFDiv(BinaryOperator &I);
286 Value *simplifyRangeCheck(ICmpInst *Cmp0, ICmpInst *Cmp1, bool Inverted);
287 Instruction *visitAnd(BinaryOperator &I);
288 Instruction *visitOr(BinaryOperator &I);
289 Instruction *visitXor(BinaryOperator &I);
290 Instruction *visitShl(BinaryOperator &I);
291 Instruction *visitAShr(BinaryOperator &I);
292 Instruction *visitLShr(BinaryOperator &I);
293 Instruction *commonShiftTransforms(BinaryOperator &I);
294 Instruction *visitFCmpInst(FCmpInst &I);
295 Instruction *visitICmpInst(ICmpInst &I);
296 Instruction *FoldShiftByConstant(Value *Op0, Constant *Op1,
298 Instruction *commonCastTransforms(CastInst &CI);
299 Instruction *commonPointerCastTransforms(CastInst &CI);
300 Instruction *visitTrunc(TruncInst &CI);
301 Instruction *visitZExt(ZExtInst &CI);
302 Instruction *visitSExt(SExtInst &CI);
303 Instruction *visitFPTrunc(FPTruncInst &CI);
304 Instruction *visitFPExt(CastInst &CI);
305 Instruction *visitFPToUI(FPToUIInst &FI);
306 Instruction *visitFPToSI(FPToSIInst &FI);
307 Instruction *visitUIToFP(CastInst &CI);
308 Instruction *visitSIToFP(CastInst &CI);
309 Instruction *visitPtrToInt(PtrToIntInst &CI);
310 Instruction *visitIntToPtr(IntToPtrInst &CI);
311 Instruction *visitBitCast(BitCastInst &CI);
312 Instruction *visitAddrSpaceCast(AddrSpaceCastInst &CI);
313 Instruction *FoldItoFPtoI(Instruction &FI);
314 Instruction *visitSelectInst(SelectInst &SI);
315 Instruction *visitCallInst(CallInst &CI);
316 Instruction *visitInvokeInst(InvokeInst &II);
318 Instruction *SliceUpIllegalIntegerPHI(PHINode &PN);
319 Instruction *visitPHINode(PHINode &PN);
320 Instruction *visitGetElementPtrInst(GetElementPtrInst &GEP);
321 Instruction *visitAllocaInst(AllocaInst &AI);
322 Instruction *visitAllocSite(Instruction &FI);
323 Instruction *visitFree(CallInst &FI);
324 Instruction *visitLoadInst(LoadInst &LI);
325 Instruction *visitStoreInst(StoreInst &SI);
326 Instruction *visitBranchInst(BranchInst &BI);
327 Instruction *visitFenceInst(FenceInst &FI);
328 Instruction *visitSwitchInst(SwitchInst &SI);
329 Instruction *visitReturnInst(ReturnInst &RI);
330 Instruction *visitInsertValueInst(InsertValueInst &IV);
331 Instruction *visitInsertElementInst(InsertElementInst &IE);
332 Instruction *visitExtractElementInst(ExtractElementInst &EI);
333 Instruction *visitShuffleVectorInst(ShuffleVectorInst &SVI);
334 Instruction *visitExtractValueInst(ExtractValueInst &EV);
335 Instruction *visitLandingPadInst(LandingPadInst &LI);
336 Instruction *visitVAStartInst(VAStartInst &I);
337 Instruction *visitVACopyInst(VACopyInst &I);
339 /// Specify what to return for unhandled instructions.
340 Instruction *visitInstruction(Instruction &I) { return nullptr; }
342 /// True when DB dominates all uses of DI except UI.
343 /// UI must be in the same block as DI.
344 /// The routine checks that the DI parent and DB are different.
345 bool dominatesAllUses(const Instruction *DI, const Instruction *UI,
346 const BasicBlock *DB) const;
348 /// Try to replace select with select operand SIOpd in SI-ICmp sequence.
349 bool replacedSelectWithOperand(SelectInst *SI, const ICmpInst *Icmp,
350 const unsigned SIOpd);
352 /// Try to replace instruction \p I with value \p V which are pointers
353 /// in different address space.
354 /// \return true if successful.
355 bool replacePointer(Instruction &I, Value *V);
358 bool shouldChangeType(unsigned FromBitWidth, unsigned ToBitWidth) const;
359 bool shouldChangeType(Type *From, Type *To) const;
360 Value *dyn_castNegVal(Value *V) const;
361 Value *dyn_castFNegVal(Value *V, bool NoSignedZero = false) const;
362 Type *FindElementAtOffset(PointerType *PtrTy, int64_t Offset,
363 SmallVectorImpl<Value *> &NewIndices);
365 /// Classify whether a cast is worth optimizing.
367 /// This is a helper to decide whether the simplification of
368 /// logic(cast(A), cast(B)) to cast(logic(A, B)) should be performed.
370 /// \param CI The cast we are interested in.
372 /// \return true if this cast actually results in any code being generated and
373 /// if it cannot already be eliminated by some other transformation.
374 bool shouldOptimizeCast(CastInst *CI);
376 /// \brief Try to optimize a sequence of instructions checking if an operation
377 /// on LHS and RHS overflows.
379 /// If this overflow check is done via one of the overflow check intrinsics,
380 /// then CtxI has to be the call instruction calling that intrinsic. If this
381 /// overflow check is done by arithmetic followed by a compare, then CtxI has
382 /// to be the arithmetic instruction.
384 /// If a simplification is possible, stores the simplified result of the
385 /// operation in OperationResult and result of the overflow check in
386 /// OverflowResult, and return true. If no simplification is possible,
388 bool OptimizeOverflowCheck(OverflowCheckFlavor OCF, Value *LHS, Value *RHS,
389 Instruction &CtxI, Value *&OperationResult,
390 Constant *&OverflowResult);
392 Instruction *visitCallSite(CallSite CS);
393 Instruction *tryOptimizeCall(CallInst *CI);
394 bool transformConstExprCastCall(CallSite CS);
395 Instruction *transformCallThroughTrampoline(CallSite CS,
396 IntrinsicInst *Tramp);
398 /// Transform (zext icmp) to bitwise / integer operations in order to
401 /// \param ICI The icmp of the (zext icmp) pair we are interested in.
402 /// \parem CI The zext of the (zext icmp) pair we are interested in.
403 /// \param DoTransform Pass false to just test whether the given (zext icmp)
404 /// would be transformed. Pass true to actually perform the transformation.
406 /// \return null if the transformation cannot be performed. If the
407 /// transformation can be performed the new instruction that replaces the
408 /// (zext icmp) pair will be returned (if \p DoTransform is false the
409 /// unmodified \p ICI will be returned in this case).
410 Instruction *transformZExtICmp(ICmpInst *ICI, ZExtInst &CI,
411 bool DoTransform = true);
413 Instruction *transformSExtICmp(ICmpInst *ICI, Instruction &CI);
414 bool willNotOverflowSignedAdd(const Value *LHS, const Value *RHS,
415 const Instruction &CxtI) const {
416 return computeOverflowForSignedAdd(LHS, RHS, &CxtI) ==
417 OverflowResult::NeverOverflows;
419 bool willNotOverflowUnsignedAdd(const Value *LHS, const Value *RHS,
420 const Instruction &CxtI) const {
421 return computeOverflowForUnsignedAdd(LHS, RHS, &CxtI) ==
422 OverflowResult::NeverOverflows;
424 bool willNotOverflowSignedSub(const Value *LHS, const Value *RHS,
425 const Instruction &CxtI) const;
426 bool willNotOverflowUnsignedSub(const Value *LHS, const Value *RHS,
427 const Instruction &CxtI) const;
428 bool willNotOverflowSignedMul(const Value *LHS, const Value *RHS,
429 const Instruction &CxtI) const;
430 bool willNotOverflowUnsignedMul(const Value *LHS, const Value *RHS,
431 const Instruction &CxtI) const {
432 return computeOverflowForUnsignedMul(LHS, RHS, &CxtI) ==
433 OverflowResult::NeverOverflows;
435 Value *EmitGEPOffset(User *GEP);
436 Instruction *scalarizePHI(ExtractElementInst &EI, PHINode *PN);
437 Value *EvaluateInDifferentElementOrder(Value *V, ArrayRef<int> Mask);
438 Instruction *foldCastedBitwiseLogic(BinaryOperator &I);
439 Instruction *shrinkBitwiseLogic(TruncInst &Trunc);
440 Instruction *optimizeBitCastFromPhi(CastInst &CI, PHINode *PN);
442 /// Determine if a pair of casts can be replaced by a single cast.
444 /// \param CI1 The first of a pair of casts.
445 /// \param CI2 The second of a pair of casts.
447 /// \return 0 if the cast pair cannot be eliminated, otherwise returns an
448 /// Instruction::CastOps value for a cast that can replace the pair, casting
449 /// CI1->getSrcTy() to CI2->getDstTy().
451 /// \see CastInst::isEliminableCastPair
452 Instruction::CastOps isEliminableCastPair(const CastInst *CI1,
453 const CastInst *CI2);
455 Value *foldAndOfICmps(ICmpInst *LHS, ICmpInst *RHS, Instruction &CxtI);
456 Value *foldAndOfFCmps(FCmpInst *LHS, FCmpInst *RHS);
457 Value *foldOrOfICmps(ICmpInst *LHS, ICmpInst *RHS, Instruction &CxtI);
458 Value *foldOrOfFCmps(FCmpInst *LHS, FCmpInst *RHS);
459 Value *foldXorOfICmps(ICmpInst *LHS, ICmpInst *RHS);
461 Value *foldAndOrOfICmpsOfAndWithPow2(ICmpInst *LHS, ICmpInst *RHS,
462 bool JoinedByAnd, Instruction &CxtI);
464 /// \brief Inserts an instruction \p New before instruction \p Old
466 /// Also adds the new instruction to the worklist and returns \p New so that
467 /// it is suitable for use as the return from the visitation patterns.
468 Instruction *InsertNewInstBefore(Instruction *New, Instruction &Old) {
469 assert(New && !New->getParent() &&
470 "New instruction already inserted into a basic block!");
471 BasicBlock *BB = Old.getParent();
472 BB->getInstList().insert(Old.getIterator(), New); // Insert inst
477 /// \brief Same as InsertNewInstBefore, but also sets the debug loc.
478 Instruction *InsertNewInstWith(Instruction *New, Instruction &Old) {
479 New->setDebugLoc(Old.getDebugLoc());
480 return InsertNewInstBefore(New, Old);
483 /// \brief A combiner-aware RAUW-like routine.
485 /// This method is to be used when an instruction is found to be dead,
486 /// replaceable with another preexisting expression. Here we add all uses of
487 /// I to the worklist, replace all uses of I with the new value, then return
488 /// I, so that the inst combiner will know that I was modified.
489 Instruction *replaceInstUsesWith(Instruction &I, Value *V) {
490 // If there are no uses to replace, then we return nullptr to indicate that
491 // no changes were made to the program.
492 if (I.use_empty()) return nullptr;
494 Worklist.AddUsersToWorkList(I); // Add all modified instrs to worklist.
496 // If we are replacing the instruction with itself, this must be in a
497 // segment of unreachable code, so just clobber the instruction.
499 V = UndefValue::get(I.getType());
501 DEBUG(dbgs() << "IC: Replacing " << I << "\n"
502 << " with " << *V << '\n');
504 I.replaceAllUsesWith(V);
508 /// Creates a result tuple for an overflow intrinsic \p II with a given
509 /// \p Result and a constant \p Overflow value.
510 Instruction *CreateOverflowTuple(IntrinsicInst *II, Value *Result,
511 Constant *Overflow) {
512 Constant *V[] = {UndefValue::get(Result->getType()), Overflow};
513 StructType *ST = cast<StructType>(II->getType());
514 Constant *Struct = ConstantStruct::get(ST, V);
515 return InsertValueInst::Create(Struct, Result, 0);
518 /// \brief Combiner aware instruction erasure.
520 /// When dealing with an instruction that has side effects or produces a void
521 /// value, we can't rely on DCE to delete the instruction. Instead, visit
522 /// methods should return the value returned by this function.
523 Instruction *eraseInstFromFunction(Instruction &I) {
524 DEBUG(dbgs() << "IC: ERASE " << I << '\n');
525 assert(I.use_empty() && "Cannot erase instruction that is used!");
528 // Make sure that we reprocess all operands now that we reduced their
530 if (I.getNumOperands() < 8) {
531 for (Use &Operand : I.operands())
532 if (auto *Inst = dyn_cast<Instruction>(Operand))
538 return nullptr; // Don't do anything with FI
541 void computeKnownBits(const Value *V, KnownBits &Known,
542 unsigned Depth, const Instruction *CxtI) const {
543 llvm::computeKnownBits(V, Known, DL, Depth, &AC, CxtI, &DT);
545 KnownBits computeKnownBits(const Value *V, unsigned Depth,
546 const Instruction *CxtI) const {
547 return llvm::computeKnownBits(V, DL, Depth, &AC, CxtI, &DT);
550 bool isKnownToBeAPowerOfTwo(const Value *V, bool OrZero = false,
552 const Instruction *CxtI = nullptr) {
553 return llvm::isKnownToBeAPowerOfTwo(V, DL, OrZero, Depth, &AC, CxtI, &DT);
556 bool MaskedValueIsZero(const Value *V, const APInt &Mask, unsigned Depth = 0,
557 const Instruction *CxtI = nullptr) const {
558 return llvm::MaskedValueIsZero(V, Mask, DL, Depth, &AC, CxtI, &DT);
560 unsigned ComputeNumSignBits(const Value *Op, unsigned Depth = 0,
561 const Instruction *CxtI = nullptr) const {
562 return llvm::ComputeNumSignBits(Op, DL, Depth, &AC, CxtI, &DT);
564 OverflowResult computeOverflowForUnsignedMul(const Value *LHS,
566 const Instruction *CxtI) const {
567 return llvm::computeOverflowForUnsignedMul(LHS, RHS, DL, &AC, CxtI, &DT);
569 OverflowResult computeOverflowForUnsignedAdd(const Value *LHS,
571 const Instruction *CxtI) const {
572 return llvm::computeOverflowForUnsignedAdd(LHS, RHS, DL, &AC, CxtI, &DT);
574 OverflowResult computeOverflowForSignedAdd(const Value *LHS,
576 const Instruction *CxtI) const {
577 return llvm::computeOverflowForSignedAdd(LHS, RHS, DL, &AC, CxtI, &DT);
580 /// Maximum size of array considered when transforming.
581 uint64_t MaxArraySizeForCombine;
584 /// \brief Performs a few simplifications for operators which are associative
586 bool SimplifyAssociativeOrCommutative(BinaryOperator &I);
588 /// \brief Tries to simplify binary operations which some other binary
589 /// operation distributes over.
591 /// It does this by either by factorizing out common terms (eg "(A*B)+(A*C)"
592 /// -> "A*(B+C)") or expanding out if this results in simplifications (eg: "A
593 /// & (B | C) -> (A&B) | (A&C)" if this is a win). Returns the simplified
594 /// value, or null if it didn't simplify.
595 Value *SimplifyUsingDistributiveLaws(BinaryOperator &I);
597 /// This tries to simplify binary operations by factorizing out common terms
598 /// (e. g. "(A*B)+(A*C)" -> "A*(B+C)").
599 Value *tryFactorization(BinaryOperator &, Instruction::BinaryOps, Value *,
600 Value *, Value *, Value *);
602 /// Match a select chain which produces one of three values based on whether
603 /// the LHS is less than, equal to, or greater than RHS respectively.
604 /// Return true if we matched a three way compare idiom. The LHS, RHS, Less,
605 /// Equal and Greater values are saved in the matching process and returned to
607 bool matchThreeWayIntCompare(SelectInst *SI, Value *&LHS, Value *&RHS,
608 ConstantInt *&Less, ConstantInt *&Equal,
609 ConstantInt *&Greater);
611 /// \brief Attempts to replace V with a simpler value based on the demanded
613 Value *SimplifyDemandedUseBits(Value *V, APInt DemandedMask, KnownBits &Known,
614 unsigned Depth, Instruction *CxtI);
615 bool SimplifyDemandedBits(Instruction *I, unsigned Op,
616 const APInt &DemandedMask, KnownBits &Known,
618 /// Helper routine of SimplifyDemandedUseBits. It computes KnownZero/KnownOne
619 /// bits. It also tries to handle simplifications that can be done based on
620 /// DemandedMask, but without modifying the Instruction.
621 Value *SimplifyMultipleUseDemandedBits(Instruction *I,
622 const APInt &DemandedMask,
624 unsigned Depth, Instruction *CxtI);
625 /// Helper routine of SimplifyDemandedUseBits. It tries to simplify demanded
626 /// bit for "r1 = shr x, c1; r2 = shl r1, c2" instruction sequence.
627 Value *simplifyShrShlDemandedBits(
628 Instruction *Shr, const APInt &ShrOp1, Instruction *Shl,
629 const APInt &ShlOp1, const APInt &DemandedMask, KnownBits &Known);
631 /// \brief Tries to simplify operands to an integer instruction based on its
633 bool SimplifyDemandedInstructionBits(Instruction &Inst);
635 Value *SimplifyDemandedVectorElts(Value *V, APInt DemandedElts,
636 APInt &UndefElts, unsigned Depth = 0);
638 Value *SimplifyVectorOp(BinaryOperator &Inst);
641 /// Given a binary operator, cast instruction, or select which has a PHI node
642 /// as operand #0, see if we can fold the instruction into the PHI (which is
643 /// only possible if all operands to the PHI are constants).
644 Instruction *foldOpIntoPhi(Instruction &I, PHINode *PN);
646 /// Given an instruction with a select as one operand and a constant as the
647 /// other operand, try to fold the binary operator into the select arguments.
648 /// This also works for Cast instructions, which obviously do not have a
650 Instruction *FoldOpIntoSelect(Instruction &Op, SelectInst *SI);
652 /// This is a convenience wrapper function for the above two functions.
653 Instruction *foldOpWithConstantIntoOperand(BinaryOperator &I);
655 /// \brief Try to rotate an operation below a PHI node, using PHI nodes for
657 Instruction *FoldPHIArgOpIntoPHI(PHINode &PN);
658 Instruction *FoldPHIArgBinOpIntoPHI(PHINode &PN);
659 Instruction *FoldPHIArgGEPIntoPHI(PHINode &PN);
660 Instruction *FoldPHIArgLoadIntoPHI(PHINode &PN);
661 Instruction *FoldPHIArgZextsIntoPHI(PHINode &PN);
663 /// Helper function for FoldPHIArgXIntoPHI() to get debug location for the
664 /// folded operation.
665 DebugLoc PHIArgMergedDebugLoc(PHINode &PN);
667 Instruction *foldGEPICmp(GEPOperator *GEPLHS, Value *RHS,
668 ICmpInst::Predicate Cond, Instruction &I);
669 Instruction *foldAllocaCmp(ICmpInst &ICI, const AllocaInst *Alloca,
671 Instruction *foldCmpLoadFromIndexedGlobal(GetElementPtrInst *GEP,
672 GlobalVariable *GV, CmpInst &ICI,
673 ConstantInt *AndCst = nullptr);
674 Instruction *foldFCmpIntToFPConst(FCmpInst &I, Instruction *LHSI,
676 Instruction *foldICmpAddOpConst(Instruction &ICI, Value *X, ConstantInt *CI,
677 ICmpInst::Predicate Pred);
678 Instruction *foldICmpWithCastAndCast(ICmpInst &ICI);
680 Instruction *foldICmpUsingKnownBits(ICmpInst &Cmp);
681 Instruction *foldICmpWithConstant(ICmpInst &Cmp);
682 Instruction *foldICmpInstWithConstant(ICmpInst &Cmp);
683 Instruction *foldICmpInstWithConstantNotInt(ICmpInst &Cmp);
684 Instruction *foldICmpBinOp(ICmpInst &Cmp);
685 Instruction *foldICmpEquality(ICmpInst &Cmp);
687 Instruction *foldICmpSelectConstant(ICmpInst &Cmp, Instruction *Select,
689 Instruction *foldICmpTruncConstant(ICmpInst &Cmp, Instruction *Trunc,
691 Instruction *foldICmpAndConstant(ICmpInst &Cmp, BinaryOperator *And,
693 Instruction *foldICmpXorConstant(ICmpInst &Cmp, BinaryOperator *Xor,
695 Instruction *foldICmpOrConstant(ICmpInst &Cmp, BinaryOperator *Or,
697 Instruction *foldICmpMulConstant(ICmpInst &Cmp, BinaryOperator *Mul,
699 Instruction *foldICmpShlConstant(ICmpInst &Cmp, BinaryOperator *Shl,
701 Instruction *foldICmpShrConstant(ICmpInst &Cmp, BinaryOperator *Shr,
703 Instruction *foldICmpUDivConstant(ICmpInst &Cmp, BinaryOperator *UDiv,
705 Instruction *foldICmpDivConstant(ICmpInst &Cmp, BinaryOperator *Div,
707 Instruction *foldICmpSubConstant(ICmpInst &Cmp, BinaryOperator *Sub,
709 Instruction *foldICmpAddConstant(ICmpInst &Cmp, BinaryOperator *Add,
711 Instruction *foldICmpAndConstConst(ICmpInst &Cmp, BinaryOperator *And,
713 Instruction *foldICmpAndShift(ICmpInst &Cmp, BinaryOperator *And,
714 const APInt *C1, const APInt *C2);
715 Instruction *foldICmpShrConstConst(ICmpInst &I, Value *ShAmt, const APInt &C1,
717 Instruction *foldICmpShlConstConst(ICmpInst &I, Value *ShAmt, const APInt &C1,
720 Instruction *foldICmpBinOpEqualityWithConstant(ICmpInst &Cmp,
723 Instruction *foldICmpIntrinsicWithConstant(ICmpInst &ICI, const APInt *C);
725 // Helpers of visitSelectInst().
726 Instruction *foldSelectExtConst(SelectInst &Sel);
727 Instruction *foldSelectOpOp(SelectInst &SI, Instruction *TI, Instruction *FI);
728 Instruction *foldSelectIntoOp(SelectInst &SI, Value *, Value *);
729 Instruction *foldSPFofSPF(Instruction *Inner, SelectPatternFlavor SPF1,
730 Value *A, Value *B, Instruction &Outer,
731 SelectPatternFlavor SPF2, Value *C);
732 Instruction *foldSelectInstWithICmp(SelectInst &SI, ICmpInst *ICI);
734 Instruction *OptAndOp(BinaryOperator *Op, ConstantInt *OpRHS,
735 ConstantInt *AndRHS, BinaryOperator &TheAnd);
737 Value *insertRangeTest(Value *V, const APInt &Lo, const APInt &Hi,
738 bool isSigned, bool Inside);
739 Instruction *PromoteCastOfAllocation(BitCastInst &CI, AllocaInst &AI);
740 Instruction *MatchBSwap(BinaryOperator &I);
741 bool SimplifyStoreAtEndOfBlock(StoreInst &SI);
744 SimplifyElementUnorderedAtomicMemCpy(ElementUnorderedAtomicMemCpyInst *AMI);
745 Instruction *SimplifyMemTransfer(MemIntrinsic *MI);
746 Instruction *SimplifyMemSet(MemSetInst *MI);
748 Value *EvaluateInDifferentType(Value *V, Type *Ty, bool isSigned);
750 /// \brief Returns a value X such that Val = X * Scale, or null if none.
752 /// If the multiplication is known not to overflow then NoSignedWrap is set.
753 Value *Descale(Value *Val, APInt Scale, bool &NoSignedWrap);
756 } // end namespace llvm.