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