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 //===----------------------------------------------------------------------===//
12 /// This file provides internal interfaces used to implement the InstCombine.
14 //===----------------------------------------------------------------------===//
16 #ifndef LLVM_LIB_TRANSFORMS_INSTCOMBINE_INSTCOMBINEINTERNAL_H
17 #define LLVM_LIB_TRANSFORMS_INSTCOMBINE_INSTCOMBINEINTERNAL_H
19 #include "llvm/ADT/ArrayRef.h"
20 #include "llvm/Analysis/AliasAnalysis.h"
21 #include "llvm/Analysis/InstructionSimplify.h"
22 #include "llvm/Analysis/TargetFolder.h"
23 #include "llvm/Analysis/ValueTracking.h"
24 #include "llvm/IR/Argument.h"
25 #include "llvm/IR/BasicBlock.h"
26 #include "llvm/IR/Constant.h"
27 #include "llvm/IR/Constants.h"
28 #include "llvm/IR/DerivedTypes.h"
29 #include "llvm/IR/IRBuilder.h"
30 #include "llvm/IR/InstVisitor.h"
31 #include "llvm/IR/InstrTypes.h"
32 #include "llvm/IR/Instruction.h"
33 #include "llvm/IR/IntrinsicInst.h"
34 #include "llvm/IR/Intrinsics.h"
35 #include "llvm/IR/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"
47 #define DEBUG_TYPE "instcombine"
52 class AssumptionCache;
59 class OptimizationRemarkEmitter;
60 class TargetLibraryInfo;
63 /// Assign a complexity or rank value to LLVM Values. This is used to reduce
64 /// the amount of pattern matching needed for compares and commutative
65 /// instructions. For example, if we have:
66 /// icmp ugt X, Constant
68 /// xor (add X, Constant), cast Z
70 /// We do not have to consider the commuted variants of these patterns because
71 /// canonicalization based on complexity guarantees the above ordering.
73 /// This routine maps IR values to various complexity ranks:
76 /// 2 -> Other non-instructions
78 /// 4 -> Cast and (f)neg/not instructions
79 /// 5 -> Other instructions
80 static inline unsigned getComplexity(Value *V) {
81 if (isa<Instruction>(V)) {
82 if (isa<CastInst>(V) || BinaryOperator::isNeg(V) ||
83 BinaryOperator::isFNeg(V) || BinaryOperator::isNot(V))
89 return isa<Constant>(V) ? (isa<UndefValue>(V) ? 0 : 1) : 2;
92 /// Predicate canonicalization reduces the number of patterns that need to be
93 /// matched by other transforms. For example, we may swap the operands of a
94 /// conditional branch or select to create a compare with a canonical (inverted)
95 /// predicate which is then more likely to be matched with other values.
96 static inline bool isCanonicalPredicate(CmpInst::Predicate Pred) {
98 case CmpInst::ICMP_NE:
99 case CmpInst::ICMP_ULE:
100 case CmpInst::ICMP_SLE:
101 case CmpInst::ICMP_UGE:
102 case CmpInst::ICMP_SGE:
103 // TODO: There are 16 FCMP predicates. Should others be (not) canonical?
104 case CmpInst::FCMP_ONE:
105 case CmpInst::FCMP_OLE:
106 case CmpInst::FCMP_OGE:
113 /// Return the source operand of a potentially bitcasted value while optionally
114 /// checking if it has one use. If there is no bitcast or the one use check is
115 /// not met, return the input value itself.
116 static inline Value *peekThroughBitcast(Value *V, bool OneUseOnly = false) {
117 if (auto *BitCast = dyn_cast<BitCastInst>(V))
118 if (!OneUseOnly || BitCast->hasOneUse())
119 return BitCast->getOperand(0);
121 // V is not a bitcast or V has more than one use and OneUseOnly is true.
125 /// \brief Add one to a Constant
126 static inline Constant *AddOne(Constant *C) {
127 return ConstantExpr::getAdd(C, ConstantInt::get(C->getType(), 1));
130 /// \brief Subtract one from a Constant
131 static inline Constant *SubOne(Constant *C) {
132 return ConstantExpr::getSub(C, ConstantInt::get(C->getType(), 1));
135 /// \brief Return true if the specified value is free to invert (apply ~ to).
136 /// This happens in cases where the ~ can be eliminated. If WillInvertAllUses
137 /// is true, work under the assumption that the caller intends to remove all
138 /// uses of V and only keep uses of ~V.
139 static inline bool IsFreeToInvert(Value *V, bool WillInvertAllUses) {
141 if (BinaryOperator::isNot(V))
144 // Constants can be considered to be not'ed values.
145 if (isa<ConstantInt>(V))
148 // A vector of constant integers can be inverted easily.
149 if (V->getType()->isVectorTy() && isa<Constant>(V)) {
150 unsigned NumElts = V->getType()->getVectorNumElements();
151 for (unsigned i = 0; i != NumElts; ++i) {
152 Constant *Elt = cast<Constant>(V)->getAggregateElement(i);
156 if (isa<UndefValue>(Elt))
159 if (!isa<ConstantInt>(Elt))
165 // Compares can be inverted if all of their uses are being modified to use the
168 return WillInvertAllUses;
170 // If `V` is of the form `A + Constant` then `-1 - V` can be folded into `(-1
171 // - Constant) - A` if we are willing to invert all of the uses.
172 if (BinaryOperator *BO = dyn_cast<BinaryOperator>(V))
173 if (BO->getOpcode() == Instruction::Add ||
174 BO->getOpcode() == Instruction::Sub)
175 if (isa<Constant>(BO->getOperand(0)) || isa<Constant>(BO->getOperand(1)))
176 return WillInvertAllUses;
181 /// \brief Specific patterns of overflow check idioms that we match.
182 enum OverflowCheckFlavor {
193 /// \brief Returns the OverflowCheckFlavor corresponding to a overflow_with_op
195 static inline OverflowCheckFlavor
196 IntrinsicIDToOverflowCheckFlavor(unsigned ID) {
200 case Intrinsic::uadd_with_overflow:
201 return OCF_UNSIGNED_ADD;
202 case Intrinsic::sadd_with_overflow:
203 return OCF_SIGNED_ADD;
204 case Intrinsic::usub_with_overflow:
205 return OCF_UNSIGNED_SUB;
206 case Intrinsic::ssub_with_overflow:
207 return OCF_SIGNED_SUB;
208 case Intrinsic::umul_with_overflow:
209 return OCF_UNSIGNED_MUL;
210 case Intrinsic::smul_with_overflow:
211 return OCF_SIGNED_MUL;
215 /// \brief The core instruction combiner logic.
217 /// This class provides both the logic to recursively visit instructions and
219 class LLVM_LIBRARY_VISIBILITY InstCombiner
220 : public InstVisitor<InstCombiner, Instruction *> {
221 // FIXME: These members shouldn't be public.
223 /// \brief A worklist of the instructions that need to be simplified.
224 InstCombineWorklist &Worklist;
226 /// \brief An IRBuilder that automatically inserts new instructions into the
228 using BuilderTy = IRBuilder<TargetFolder, IRBuilderCallbackInserter>;
232 // Mode in which we are running the combiner.
233 const bool MinimizeSize;
235 /// Enable combines that trigger rarely but are costly in compiletime.
236 const bool ExpensiveCombines;
240 // Required analyses.
242 TargetLibraryInfo &TLI;
244 const DataLayout &DL;
245 const SimplifyQuery SQ;
246 OptimizationRemarkEmitter &ORE;
248 // Optional analyses. When non-null, these can both be used to do better
249 // combining and will be updated to reflect any changes.
252 bool MadeIRChange = false;
255 InstCombiner(InstCombineWorklist &Worklist, BuilderTy &Builder,
256 bool MinimizeSize, bool ExpensiveCombines, AliasAnalysis *AA,
257 AssumptionCache &AC, TargetLibraryInfo &TLI, DominatorTree &DT,
258 OptimizationRemarkEmitter &ORE, const DataLayout &DL,
260 : Worklist(Worklist), Builder(Builder), MinimizeSize(MinimizeSize),
261 ExpensiveCombines(ExpensiveCombines), AA(AA), AC(AC), TLI(TLI), DT(DT),
262 DL(DL), SQ(DL, &TLI, &DT, &AC), ORE(ORE), LI(LI) {}
264 /// \brief Run the combiner over the entire worklist until it is empty.
266 /// \returns true if the IR is changed.
269 AssumptionCache &getAssumptionCache() const { return AC; }
271 const DataLayout &getDataLayout() const { return DL; }
273 DominatorTree &getDominatorTree() const { return DT; }
275 LoopInfo *getLoopInfo() const { return LI; }
277 TargetLibraryInfo &getTargetLibraryInfo() const { return TLI; }
279 // Visitation implementation - Implement instruction combining for different
280 // instruction types. The semantics are as follows:
282 // null - No change was made
283 // I - Change was made, I is still valid, I may be dead though
284 // otherwise - Change was made, replace I with returned instruction
286 Instruction *visitAdd(BinaryOperator &I);
287 Instruction *visitFAdd(BinaryOperator &I);
288 Value *OptimizePointerDifference(Value *LHS, Value *RHS, Type *Ty);
289 Instruction *visitSub(BinaryOperator &I);
290 Instruction *visitFSub(BinaryOperator &I);
291 Instruction *visitMul(BinaryOperator &I);
292 Value *foldFMulConst(Instruction *FMulOrDiv, Constant *C,
293 Instruction *InsertBefore);
294 Instruction *visitFMul(BinaryOperator &I);
295 Instruction *visitURem(BinaryOperator &I);
296 Instruction *visitSRem(BinaryOperator &I);
297 Instruction *visitFRem(BinaryOperator &I);
298 bool simplifyDivRemOfSelectWithZeroOp(BinaryOperator &I);
299 Instruction *commonRemTransforms(BinaryOperator &I);
300 Instruction *commonIRemTransforms(BinaryOperator &I);
301 Instruction *commonDivTransforms(BinaryOperator &I);
302 Instruction *commonIDivTransforms(BinaryOperator &I);
303 Instruction *visitUDiv(BinaryOperator &I);
304 Instruction *visitSDiv(BinaryOperator &I);
305 Instruction *visitFDiv(BinaryOperator &I);
306 Value *simplifyRangeCheck(ICmpInst *Cmp0, ICmpInst *Cmp1, bool Inverted);
307 Instruction *visitAnd(BinaryOperator &I);
308 Instruction *visitOr(BinaryOperator &I);
309 Instruction *visitXor(BinaryOperator &I);
310 Instruction *visitShl(BinaryOperator &I);
311 Instruction *visitAShr(BinaryOperator &I);
312 Instruction *visitLShr(BinaryOperator &I);
313 Instruction *commonShiftTransforms(BinaryOperator &I);
314 Instruction *visitFCmpInst(FCmpInst &I);
315 Instruction *visitICmpInst(ICmpInst &I);
316 Instruction *FoldShiftByConstant(Value *Op0, Constant *Op1,
318 Instruction *commonCastTransforms(CastInst &CI);
319 Instruction *commonPointerCastTransforms(CastInst &CI);
320 Instruction *visitTrunc(TruncInst &CI);
321 Instruction *visitZExt(ZExtInst &CI);
322 Instruction *visitSExt(SExtInst &CI);
323 Instruction *visitFPTrunc(FPTruncInst &CI);
324 Instruction *visitFPExt(CastInst &CI);
325 Instruction *visitFPToUI(FPToUIInst &FI);
326 Instruction *visitFPToSI(FPToSIInst &FI);
327 Instruction *visitUIToFP(CastInst &CI);
328 Instruction *visitSIToFP(CastInst &CI);
329 Instruction *visitPtrToInt(PtrToIntInst &CI);
330 Instruction *visitIntToPtr(IntToPtrInst &CI);
331 Instruction *visitBitCast(BitCastInst &CI);
332 Instruction *visitAddrSpaceCast(AddrSpaceCastInst &CI);
333 Instruction *FoldItoFPtoI(Instruction &FI);
334 Instruction *visitSelectInst(SelectInst &SI);
335 Instruction *visitCallInst(CallInst &CI);
336 Instruction *visitInvokeInst(InvokeInst &II);
338 Instruction *SliceUpIllegalIntegerPHI(PHINode &PN);
339 Instruction *visitPHINode(PHINode &PN);
340 Instruction *visitGetElementPtrInst(GetElementPtrInst &GEP);
341 Instruction *visitAllocaInst(AllocaInst &AI);
342 Instruction *visitAllocSite(Instruction &FI);
343 Instruction *visitFree(CallInst &FI);
344 Instruction *visitLoadInst(LoadInst &LI);
345 Instruction *visitStoreInst(StoreInst &SI);
346 Instruction *visitBranchInst(BranchInst &BI);
347 Instruction *visitFenceInst(FenceInst &FI);
348 Instruction *visitSwitchInst(SwitchInst &SI);
349 Instruction *visitReturnInst(ReturnInst &RI);
350 Instruction *visitInsertValueInst(InsertValueInst &IV);
351 Instruction *visitInsertElementInst(InsertElementInst &IE);
352 Instruction *visitExtractElementInst(ExtractElementInst &EI);
353 Instruction *visitShuffleVectorInst(ShuffleVectorInst &SVI);
354 Instruction *visitExtractValueInst(ExtractValueInst &EV);
355 Instruction *visitLandingPadInst(LandingPadInst &LI);
356 Instruction *visitVAStartInst(VAStartInst &I);
357 Instruction *visitVACopyInst(VACopyInst &I);
359 /// Specify what to return for unhandled instructions.
360 Instruction *visitInstruction(Instruction &I) { return nullptr; }
362 /// True when DB dominates all uses of DI except UI.
363 /// UI must be in the same block as DI.
364 /// The routine checks that the DI parent and DB are different.
365 bool dominatesAllUses(const Instruction *DI, const Instruction *UI,
366 const BasicBlock *DB) const;
368 /// Try to replace select with select operand SIOpd in SI-ICmp sequence.
369 bool replacedSelectWithOperand(SelectInst *SI, const ICmpInst *Icmp,
370 const unsigned SIOpd);
372 /// Try to replace instruction \p I with value \p V which are pointers
373 /// in different address space.
374 /// \return true if successful.
375 bool replacePointer(Instruction &I, Value *V);
378 bool shouldChangeType(unsigned FromBitWidth, unsigned ToBitWidth) const;
379 bool shouldChangeType(Type *From, Type *To) const;
380 Value *dyn_castNegVal(Value *V) const;
381 Value *dyn_castFNegVal(Value *V, bool NoSignedZero = false) const;
382 Type *FindElementAtOffset(PointerType *PtrTy, int64_t Offset,
383 SmallVectorImpl<Value *> &NewIndices);
385 /// Classify whether a cast is worth optimizing.
387 /// This is a helper to decide whether the simplification of
388 /// logic(cast(A), cast(B)) to cast(logic(A, B)) should be performed.
390 /// \param CI The cast we are interested in.
392 /// \return true if this cast actually results in any code being generated and
393 /// if it cannot already be eliminated by some other transformation.
394 bool shouldOptimizeCast(CastInst *CI);
396 /// \brief Try to optimize a sequence of instructions checking if an operation
397 /// on LHS and RHS overflows.
399 /// If this overflow check is done via one of the overflow check intrinsics,
400 /// then CtxI has to be the call instruction calling that intrinsic. If this
401 /// overflow check is done by arithmetic followed by a compare, then CtxI has
402 /// to be the arithmetic instruction.
404 /// If a simplification is possible, stores the simplified result of the
405 /// operation in OperationResult and result of the overflow check in
406 /// OverflowResult, and return true. If no simplification is possible,
408 bool OptimizeOverflowCheck(OverflowCheckFlavor OCF, Value *LHS, Value *RHS,
409 Instruction &CtxI, Value *&OperationResult,
410 Constant *&OverflowResult);
412 Instruction *visitCallSite(CallSite CS);
413 Instruction *tryOptimizeCall(CallInst *CI);
414 bool transformConstExprCastCall(CallSite CS);
415 Instruction *transformCallThroughTrampoline(CallSite CS,
416 IntrinsicInst *Tramp);
418 /// Transform (zext icmp) to bitwise / integer operations in order to
421 /// \param ICI The icmp of the (zext icmp) pair we are interested in.
422 /// \parem CI The zext of the (zext icmp) pair we are interested in.
423 /// \param DoTransform Pass false to just test whether the given (zext icmp)
424 /// would be transformed. Pass true to actually perform the transformation.
426 /// \return null if the transformation cannot be performed. If the
427 /// transformation can be performed the new instruction that replaces the
428 /// (zext icmp) pair will be returned (if \p DoTransform is false the
429 /// unmodified \p ICI will be returned in this case).
430 Instruction *transformZExtICmp(ICmpInst *ICI, ZExtInst &CI,
431 bool DoTransform = true);
433 Instruction *transformSExtICmp(ICmpInst *ICI, Instruction &CI);
435 bool willNotOverflowSignedAdd(const Value *LHS, const Value *RHS,
436 const Instruction &CxtI) const {
437 return computeOverflowForSignedAdd(LHS, RHS, &CxtI) ==
438 OverflowResult::NeverOverflows;
441 bool willNotOverflowUnsignedAdd(const Value *LHS, const Value *RHS,
442 const Instruction &CxtI) const {
443 return computeOverflowForUnsignedAdd(LHS, RHS, &CxtI) ==
444 OverflowResult::NeverOverflows;
447 bool willNotOverflowSignedSub(const Value *LHS, const Value *RHS,
448 const Instruction &CxtI) const;
449 bool willNotOverflowUnsignedSub(const Value *LHS, const Value *RHS,
450 const Instruction &CxtI) const;
451 bool willNotOverflowSignedMul(const Value *LHS, const Value *RHS,
452 const Instruction &CxtI) const;
454 bool willNotOverflowUnsignedMul(const Value *LHS, const Value *RHS,
455 const Instruction &CxtI) const {
456 return computeOverflowForUnsignedMul(LHS, RHS, &CxtI) ==
457 OverflowResult::NeverOverflows;
460 Value *EmitGEPOffset(User *GEP);
461 Instruction *scalarizePHI(ExtractElementInst &EI, PHINode *PN);
462 Value *EvaluateInDifferentElementOrder(Value *V, ArrayRef<int> Mask);
463 Instruction *foldCastedBitwiseLogic(BinaryOperator &I);
464 Instruction *narrowBinOp(TruncInst &Trunc);
465 Instruction *narrowRotate(TruncInst &Trunc);
466 Instruction *optimizeBitCastFromPhi(CastInst &CI, PHINode *PN);
468 /// Determine if a pair of casts can be replaced by a single cast.
470 /// \param CI1 The first of a pair of casts.
471 /// \param CI2 The second of a pair of casts.
473 /// \return 0 if the cast pair cannot be eliminated, otherwise returns an
474 /// Instruction::CastOps value for a cast that can replace the pair, casting
475 /// CI1->getSrcTy() to CI2->getDstTy().
477 /// \see CastInst::isEliminableCastPair
478 Instruction::CastOps isEliminableCastPair(const CastInst *CI1,
479 const CastInst *CI2);
481 Value *foldAndOfICmps(ICmpInst *LHS, ICmpInst *RHS, Instruction &CxtI);
482 Value *foldOrOfICmps(ICmpInst *LHS, ICmpInst *RHS, Instruction &CxtI);
483 Value *foldXorOfICmps(ICmpInst *LHS, ICmpInst *RHS);
485 /// Optimize (fcmp)&(fcmp) or (fcmp)|(fcmp).
486 /// NOTE: Unlike most of instcombine, this returns a Value which should
487 /// already be inserted into the function.
488 Value *foldLogicOfFCmps(FCmpInst *LHS, FCmpInst *RHS, bool IsAnd);
490 Value *foldAndOrOfICmpsOfAndWithPow2(ICmpInst *LHS, ICmpInst *RHS,
491 bool JoinedByAnd, Instruction &CxtI);
493 /// \brief Inserts an instruction \p New before instruction \p Old
495 /// Also adds the new instruction to the worklist and returns \p New so that
496 /// it is suitable for use as the return from the visitation patterns.
497 Instruction *InsertNewInstBefore(Instruction *New, Instruction &Old) {
498 assert(New && !New->getParent() &&
499 "New instruction already inserted into a basic block!");
500 BasicBlock *BB = Old.getParent();
501 BB->getInstList().insert(Old.getIterator(), New); // Insert inst
506 /// \brief Same as InsertNewInstBefore, but also sets the debug loc.
507 Instruction *InsertNewInstWith(Instruction *New, Instruction &Old) {
508 New->setDebugLoc(Old.getDebugLoc());
509 return InsertNewInstBefore(New, Old);
512 /// \brief A combiner-aware RAUW-like routine.
514 /// This method is to be used when an instruction is found to be dead,
515 /// replaceable with another preexisting expression. Here we add all uses of
516 /// I to the worklist, replace all uses of I with the new value, then return
517 /// I, so that the inst combiner will know that I was modified.
518 Instruction *replaceInstUsesWith(Instruction &I, Value *V) {
519 // If there are no uses to replace, then we return nullptr to indicate that
520 // no changes were made to the program.
521 if (I.use_empty()) return nullptr;
523 Worklist.AddUsersToWorkList(I); // Add all modified instrs to worklist.
525 // If we are replacing the instruction with itself, this must be in a
526 // segment of unreachable code, so just clobber the instruction.
528 V = UndefValue::get(I.getType());
530 DEBUG(dbgs() << "IC: Replacing " << I << "\n"
531 << " with " << *V << '\n');
533 I.replaceAllUsesWith(V);
537 /// Creates a result tuple for an overflow intrinsic \p II with a given
538 /// \p Result and a constant \p Overflow value.
539 Instruction *CreateOverflowTuple(IntrinsicInst *II, Value *Result,
540 Constant *Overflow) {
541 Constant *V[] = {UndefValue::get(Result->getType()), Overflow};
542 StructType *ST = cast<StructType>(II->getType());
543 Constant *Struct = ConstantStruct::get(ST, V);
544 return InsertValueInst::Create(Struct, Result, 0);
547 /// \brief Combiner aware instruction erasure.
549 /// When dealing with an instruction that has side effects or produces a void
550 /// value, we can't rely on DCE to delete the instruction. Instead, visit
551 /// methods should return the value returned by this function.
552 Instruction *eraseInstFromFunction(Instruction &I) {
553 DEBUG(dbgs() << "IC: ERASE " << I << '\n');
554 assert(I.use_empty() && "Cannot erase instruction that is used!");
557 // Make sure that we reprocess all operands now that we reduced their
559 if (I.getNumOperands() < 8) {
560 for (Use &Operand : I.operands())
561 if (auto *Inst = dyn_cast<Instruction>(Operand))
567 return nullptr; // Don't do anything with FI
570 void computeKnownBits(const Value *V, KnownBits &Known,
571 unsigned Depth, const Instruction *CxtI) const {
572 llvm::computeKnownBits(V, Known, DL, Depth, &AC, CxtI, &DT);
575 KnownBits computeKnownBits(const Value *V, unsigned Depth,
576 const Instruction *CxtI) const {
577 return llvm::computeKnownBits(V, DL, Depth, &AC, CxtI, &DT);
580 bool isKnownToBeAPowerOfTwo(const Value *V, bool OrZero = false,
582 const Instruction *CxtI = nullptr) {
583 return llvm::isKnownToBeAPowerOfTwo(V, DL, OrZero, Depth, &AC, CxtI, &DT);
586 bool MaskedValueIsZero(const Value *V, const APInt &Mask, unsigned Depth = 0,
587 const Instruction *CxtI = nullptr) const {
588 return llvm::MaskedValueIsZero(V, Mask, DL, Depth, &AC, CxtI, &DT);
591 unsigned ComputeNumSignBits(const Value *Op, unsigned Depth = 0,
592 const Instruction *CxtI = nullptr) const {
593 return llvm::ComputeNumSignBits(Op, DL, Depth, &AC, CxtI, &DT);
596 OverflowResult computeOverflowForUnsignedMul(const Value *LHS,
598 const Instruction *CxtI) const {
599 return llvm::computeOverflowForUnsignedMul(LHS, RHS, DL, &AC, CxtI, &DT);
602 OverflowResult computeOverflowForUnsignedAdd(const Value *LHS,
604 const Instruction *CxtI) const {
605 return llvm::computeOverflowForUnsignedAdd(LHS, RHS, DL, &AC, CxtI, &DT);
608 OverflowResult computeOverflowForSignedAdd(const Value *LHS,
610 const Instruction *CxtI) const {
611 return llvm::computeOverflowForSignedAdd(LHS, RHS, DL, &AC, CxtI, &DT);
614 /// Maximum size of array considered when transforming.
615 uint64_t MaxArraySizeForCombine;
618 /// \brief Performs a few simplifications for operators which are associative
620 bool SimplifyAssociativeOrCommutative(BinaryOperator &I);
622 /// \brief Tries to simplify binary operations which some other binary
623 /// operation distributes over.
625 /// It does this by either by factorizing out common terms (eg "(A*B)+(A*C)"
626 /// -> "A*(B+C)") or expanding out if this results in simplifications (eg: "A
627 /// & (B | C) -> (A&B) | (A&C)" if this is a win). Returns the simplified
628 /// value, or null if it didn't simplify.
629 Value *SimplifyUsingDistributiveLaws(BinaryOperator &I);
631 // Binary Op helper for select operations where the expression can be
632 // efficiently reorganized.
633 Value *SimplifySelectsFeedingBinaryOp(BinaryOperator &I, Value *LHS,
636 /// This tries to simplify binary operations by factorizing out common terms
637 /// (e. g. "(A*B)+(A*C)" -> "A*(B+C)").
638 Value *tryFactorization(BinaryOperator &, Instruction::BinaryOps, Value *,
639 Value *, Value *, Value *);
641 /// Match a select chain which produces one of three values based on whether
642 /// the LHS is less than, equal to, or greater than RHS respectively.
643 /// Return true if we matched a three way compare idiom. The LHS, RHS, Less,
644 /// Equal and Greater values are saved in the matching process and returned to
646 bool matchThreeWayIntCompare(SelectInst *SI, Value *&LHS, Value *&RHS,
647 ConstantInt *&Less, ConstantInt *&Equal,
648 ConstantInt *&Greater);
650 /// \brief Attempts to replace V with a simpler value based on the demanded
652 Value *SimplifyDemandedUseBits(Value *V, APInt DemandedMask, KnownBits &Known,
653 unsigned Depth, Instruction *CxtI);
654 bool SimplifyDemandedBits(Instruction *I, unsigned Op,
655 const APInt &DemandedMask, KnownBits &Known,
658 /// Helper routine of SimplifyDemandedUseBits. It computes KnownZero/KnownOne
659 /// bits. It also tries to handle simplifications that can be done based on
660 /// DemandedMask, but without modifying the Instruction.
661 Value *SimplifyMultipleUseDemandedBits(Instruction *I,
662 const APInt &DemandedMask,
664 unsigned Depth, Instruction *CxtI);
666 /// Helper routine of SimplifyDemandedUseBits. It tries to simplify demanded
667 /// bit for "r1 = shr x, c1; r2 = shl r1, c2" instruction sequence.
668 Value *simplifyShrShlDemandedBits(
669 Instruction *Shr, const APInt &ShrOp1, Instruction *Shl,
670 const APInt &ShlOp1, const APInt &DemandedMask, KnownBits &Known);
672 /// \brief Tries to simplify operands to an integer instruction based on its
674 bool SimplifyDemandedInstructionBits(Instruction &Inst);
676 Value *SimplifyDemandedVectorElts(Value *V, APInt DemandedElts,
677 APInt &UndefElts, unsigned Depth = 0);
679 Value *SimplifyVectorOp(BinaryOperator &Inst);
682 /// Given a binary operator, cast instruction, or select which has a PHI node
683 /// as operand #0, see if we can fold the instruction into the PHI (which is
684 /// only possible if all operands to the PHI are constants).
685 Instruction *foldOpIntoPhi(Instruction &I, PHINode *PN);
687 /// Given an instruction with a select as one operand and a constant as the
688 /// other operand, try to fold the binary operator into the select arguments.
689 /// This also works for Cast instructions, which obviously do not have a
691 Instruction *FoldOpIntoSelect(Instruction &Op, SelectInst *SI);
693 /// This is a convenience wrapper function for the above two functions.
694 Instruction *foldOpWithConstantIntoOperand(BinaryOperator &I);
696 Instruction *foldAddWithConstant(BinaryOperator &Add);
698 /// \brief Try to rotate an operation below a PHI node, using PHI nodes for
700 Instruction *FoldPHIArgOpIntoPHI(PHINode &PN);
701 Instruction *FoldPHIArgBinOpIntoPHI(PHINode &PN);
702 Instruction *FoldPHIArgGEPIntoPHI(PHINode &PN);
703 Instruction *FoldPHIArgLoadIntoPHI(PHINode &PN);
704 Instruction *FoldPHIArgZextsIntoPHI(PHINode &PN);
706 /// If an integer typed PHI has only one use which is an IntToPtr operation,
707 /// replace the PHI with an existing pointer typed PHI if it exists. Otherwise
708 /// insert a new pointer typed PHI and replace the original one.
709 Instruction *FoldIntegerTypedPHI(PHINode &PN);
711 /// Helper function for FoldPHIArgXIntoPHI() to set debug location for the
712 /// folded operation.
713 void PHIArgMergedDebugLoc(Instruction *Inst, PHINode &PN);
715 Instruction *foldGEPICmp(GEPOperator *GEPLHS, Value *RHS,
716 ICmpInst::Predicate Cond, Instruction &I);
717 Instruction *foldAllocaCmp(ICmpInst &ICI, const AllocaInst *Alloca,
719 Instruction *foldCmpLoadFromIndexedGlobal(GetElementPtrInst *GEP,
720 GlobalVariable *GV, CmpInst &ICI,
721 ConstantInt *AndCst = nullptr);
722 Instruction *foldFCmpIntToFPConst(FCmpInst &I, Instruction *LHSI,
724 Instruction *foldICmpAddOpConst(Value *X, ConstantInt *CI,
725 ICmpInst::Predicate Pred);
726 Instruction *foldICmpWithCastAndCast(ICmpInst &ICI);
728 Instruction *foldICmpUsingKnownBits(ICmpInst &Cmp);
729 Instruction *foldICmpWithConstant(ICmpInst &Cmp);
730 Instruction *foldICmpInstWithConstant(ICmpInst &Cmp);
731 Instruction *foldICmpInstWithConstantNotInt(ICmpInst &Cmp);
732 Instruction *foldICmpBinOp(ICmpInst &Cmp);
733 Instruction *foldICmpEquality(ICmpInst &Cmp);
734 Instruction *foldICmpWithZero(ICmpInst &Cmp);
736 Instruction *foldICmpSelectConstant(ICmpInst &Cmp, SelectInst *Select,
738 Instruction *foldICmpTruncConstant(ICmpInst &Cmp, TruncInst *Trunc,
740 Instruction *foldICmpAndConstant(ICmpInst &Cmp, BinaryOperator *And,
742 Instruction *foldICmpXorConstant(ICmpInst &Cmp, BinaryOperator *Xor,
744 Instruction *foldICmpOrConstant(ICmpInst &Cmp, BinaryOperator *Or,
746 Instruction *foldICmpMulConstant(ICmpInst &Cmp, BinaryOperator *Mul,
748 Instruction *foldICmpShlConstant(ICmpInst &Cmp, BinaryOperator *Shl,
750 Instruction *foldICmpShrConstant(ICmpInst &Cmp, BinaryOperator *Shr,
752 Instruction *foldICmpUDivConstant(ICmpInst &Cmp, BinaryOperator *UDiv,
754 Instruction *foldICmpDivConstant(ICmpInst &Cmp, BinaryOperator *Div,
756 Instruction *foldICmpSubConstant(ICmpInst &Cmp, BinaryOperator *Sub,
758 Instruction *foldICmpAddConstant(ICmpInst &Cmp, BinaryOperator *Add,
760 Instruction *foldICmpAndConstConst(ICmpInst &Cmp, BinaryOperator *And,
762 Instruction *foldICmpAndShift(ICmpInst &Cmp, BinaryOperator *And,
763 const APInt &C1, const APInt &C2);
764 Instruction *foldICmpShrConstConst(ICmpInst &I, Value *ShAmt, const APInt &C1,
766 Instruction *foldICmpShlConstConst(ICmpInst &I, Value *ShAmt, const APInt &C1,
769 Instruction *foldICmpBinOpEqualityWithConstant(ICmpInst &Cmp,
772 Instruction *foldICmpIntrinsicWithConstant(ICmpInst &ICI, const APInt &C);
774 // Helpers of visitSelectInst().
775 Instruction *foldSelectExtConst(SelectInst &Sel);
776 Instruction *foldSelectOpOp(SelectInst &SI, Instruction *TI, Instruction *FI);
777 Instruction *foldSelectIntoOp(SelectInst &SI, Value *, Value *);
778 Instruction *foldSPFofSPF(Instruction *Inner, SelectPatternFlavor SPF1,
779 Value *A, Value *B, Instruction &Outer,
780 SelectPatternFlavor SPF2, Value *C);
781 Instruction *foldSelectInstWithICmp(SelectInst &SI, ICmpInst *ICI);
783 Instruction *OptAndOp(BinaryOperator *Op, ConstantInt *OpRHS,
784 ConstantInt *AndRHS, BinaryOperator &TheAnd);
786 Value *insertRangeTest(Value *V, const APInt &Lo, const APInt &Hi,
787 bool isSigned, bool Inside);
788 Instruction *PromoteCastOfAllocation(BitCastInst &CI, AllocaInst &AI);
789 Instruction *MatchBSwap(BinaryOperator &I);
790 bool SimplifyStoreAtEndOfBlock(StoreInst &SI);
792 Instruction *SimplifyElementUnorderedAtomicMemCpy(AtomicMemCpyInst *AMI);
793 Instruction *SimplifyMemTransfer(MemIntrinsic *MI);
794 Instruction *SimplifyMemSet(MemSetInst *MI);
796 Value *EvaluateInDifferentType(Value *V, Type *Ty, bool isSigned);
798 /// \brief Returns a value X such that Val = X * Scale, or null if none.
800 /// If the multiplication is known not to overflow then NoSignedWrap is set.
801 Value *Descale(Value *Val, APInt Scale, bool &NoSignedWrap);
804 } // end namespace llvm
808 #endif // LLVM_LIB_TRANSFORMS_INSTCOMBINE_INSTCOMBINEINTERNAL_H