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/Statistic.h"
19 #include "llvm/Analysis/InstructionSimplify.h"
20 #include "llvm/Analysis/TargetFolder.h"
21 #include "llvm/Analysis/ValueTracking.h"
22 #include "llvm/IR/IRBuilder.h"
23 #include "llvm/IR/InstVisitor.h"
24 #include "llvm/IR/PatternMatch.h"
25 #include "llvm/IR/Value.h"
26 #include "llvm/Support/Debug.h"
27 #include "llvm/Support/KnownBits.h"
28 #include "llvm/Transforms/InstCombine/InstCombiner.h"
29 #include "llvm/Transforms/Utils/Local.h"
32 #define DEBUG_TYPE "instcombine"
33 #include "llvm/Transforms/Utils/InstructionWorklist.h"
35 using namespace llvm::PatternMatch;
37 // As a default, let's assume that we want to be aggressive,
38 // and attempt to traverse with no limits in attempt to sink negation.
39 static constexpr unsigned NegatorDefaultMaxDepth = ~0U;
41 // Let's guesstimate that most often we will end up visiting/producing
42 // fairly small number of new instructions.
43 static constexpr unsigned NegatorMaxNodesSSO = 16;
49 class AssumptionCache;
50 class BlockFrequencyInfo;
56 class OptimizationRemarkEmitter;
57 class ProfileSummaryInfo;
58 class TargetLibraryInfo;
61 class LLVM_LIBRARY_VISIBILITY InstCombinerImpl final
62 : public InstCombiner,
63 public InstVisitor<InstCombinerImpl, Instruction *> {
65 InstCombinerImpl(InstructionWorklist &Worklist, BuilderTy &Builder,
66 bool MinimizeSize, AAResults *AA, AssumptionCache &AC,
67 TargetLibraryInfo &TLI, TargetTransformInfo &TTI,
68 DominatorTree &DT, OptimizationRemarkEmitter &ORE,
69 BlockFrequencyInfo *BFI, ProfileSummaryInfo *PSI,
70 const DataLayout &DL, LoopInfo *LI)
71 : InstCombiner(Worklist, Builder, MinimizeSize, AA, AC, TLI, TTI, DT, ORE,
74 virtual ~InstCombinerImpl() = default;
76 /// Run the combiner over the entire worklist until it is empty.
78 /// \returns true if the IR is changed.
81 // Visitation implementation - Implement instruction combining for different
82 // instruction types. The semantics are as follows:
84 // null - No change was made
85 // I - Change was made, I is still valid, I may be dead though
86 // otherwise - Change was made, replace I with returned instruction
88 Instruction *visitFNeg(UnaryOperator &I);
89 Instruction *visitAdd(BinaryOperator &I);
90 Instruction *visitFAdd(BinaryOperator &I);
91 Value *OptimizePointerDifference(
92 Value *LHS, Value *RHS, Type *Ty, bool isNUW);
93 Instruction *visitSub(BinaryOperator &I);
94 Instruction *visitFSub(BinaryOperator &I);
95 Instruction *visitMul(BinaryOperator &I);
96 Instruction *visitFMul(BinaryOperator &I);
97 Instruction *visitURem(BinaryOperator &I);
98 Instruction *visitSRem(BinaryOperator &I);
99 Instruction *visitFRem(BinaryOperator &I);
100 bool simplifyDivRemOfSelectWithZeroOp(BinaryOperator &I);
101 Instruction *commonIRemTransforms(BinaryOperator &I);
102 Instruction *commonIDivTransforms(BinaryOperator &I);
103 Instruction *visitUDiv(BinaryOperator &I);
104 Instruction *visitSDiv(BinaryOperator &I);
105 Instruction *visitFDiv(BinaryOperator &I);
106 Value *simplifyRangeCheck(ICmpInst *Cmp0, ICmpInst *Cmp1, bool Inverted);
107 Instruction *visitAnd(BinaryOperator &I);
108 Instruction *visitOr(BinaryOperator &I);
109 bool sinkNotIntoLogicalOp(Instruction &I);
110 bool sinkNotIntoOtherHandOfLogicalOp(Instruction &I);
111 Instruction *visitXor(BinaryOperator &I);
112 Instruction *visitShl(BinaryOperator &I);
113 Value *reassociateShiftAmtsOfTwoSameDirectionShifts(
114 BinaryOperator *Sh0, const SimplifyQuery &SQ,
115 bool AnalyzeForSignBitExtraction = false);
116 Instruction *canonicalizeCondSignextOfHighBitExtractToSignextHighBitExtract(
118 Instruction *foldVariableSignZeroExtensionOfVariableHighBitExtract(
119 BinaryOperator &OldAShr);
120 Instruction *visitAShr(BinaryOperator &I);
121 Instruction *visitLShr(BinaryOperator &I);
122 Instruction *commonShiftTransforms(BinaryOperator &I);
123 Instruction *visitFCmpInst(FCmpInst &I);
124 CmpInst *canonicalizeICmpPredicate(CmpInst &I);
125 Instruction *visitICmpInst(ICmpInst &I);
126 Instruction *FoldShiftByConstant(Value *Op0, Constant *Op1,
128 Instruction *commonCastTransforms(CastInst &CI);
129 Instruction *commonPointerCastTransforms(CastInst &CI);
130 Instruction *visitTrunc(TruncInst &CI);
131 Instruction *visitZExt(ZExtInst &Zext);
132 Instruction *visitSExt(SExtInst &Sext);
133 Instruction *visitFPTrunc(FPTruncInst &CI);
134 Instruction *visitFPExt(CastInst &CI);
135 Instruction *visitFPToUI(FPToUIInst &FI);
136 Instruction *visitFPToSI(FPToSIInst &FI);
137 Instruction *visitUIToFP(CastInst &CI);
138 Instruction *visitSIToFP(CastInst &CI);
139 Instruction *visitPtrToInt(PtrToIntInst &CI);
140 Instruction *visitIntToPtr(IntToPtrInst &CI);
141 Instruction *visitBitCast(BitCastInst &CI);
142 Instruction *visitAddrSpaceCast(AddrSpaceCastInst &CI);
143 Instruction *foldItoFPtoI(CastInst &FI);
144 Instruction *visitSelectInst(SelectInst &SI);
145 Instruction *visitCallInst(CallInst &CI);
146 Instruction *visitInvokeInst(InvokeInst &II);
147 Instruction *visitCallBrInst(CallBrInst &CBI);
149 Instruction *SliceUpIllegalIntegerPHI(PHINode &PN);
150 Instruction *visitPHINode(PHINode &PN);
151 Instruction *visitGetElementPtrInst(GetElementPtrInst &GEP);
152 Instruction *visitGEPOfGEP(GetElementPtrInst &GEP, GEPOperator *Src);
153 Instruction *visitAllocaInst(AllocaInst &AI);
154 Instruction *visitAllocSite(Instruction &FI);
155 Instruction *visitFree(CallInst &FI, Value *FreedOp);
156 Instruction *visitLoadInst(LoadInst &LI);
157 Instruction *visitStoreInst(StoreInst &SI);
158 Instruction *visitAtomicRMWInst(AtomicRMWInst &SI);
159 Instruction *visitUnconditionalBranchInst(BranchInst &BI);
160 Instruction *visitBranchInst(BranchInst &BI);
161 Instruction *visitFenceInst(FenceInst &FI);
162 Instruction *visitSwitchInst(SwitchInst &SI);
163 Instruction *visitReturnInst(ReturnInst &RI);
164 Instruction *visitUnreachableInst(UnreachableInst &I);
166 foldAggregateConstructionIntoAggregateReuse(InsertValueInst &OrigIVI);
167 Instruction *visitInsertValueInst(InsertValueInst &IV);
168 Instruction *visitInsertElementInst(InsertElementInst &IE);
169 Instruction *visitExtractElementInst(ExtractElementInst &EI);
170 Instruction *simplifyBinOpSplats(ShuffleVectorInst &SVI);
171 Instruction *visitShuffleVectorInst(ShuffleVectorInst &SVI);
172 Instruction *visitExtractValueInst(ExtractValueInst &EV);
173 Instruction *visitLandingPadInst(LandingPadInst &LI);
174 Instruction *visitVAEndInst(VAEndInst &I);
175 Value *pushFreezeToPreventPoisonFromPropagating(FreezeInst &FI);
176 bool freezeOtherUses(FreezeInst &FI);
177 Instruction *foldFreezeIntoRecurrence(FreezeInst &I, PHINode *PN);
178 Instruction *visitFreeze(FreezeInst &I);
180 /// Specify what to return for unhandled instructions.
181 Instruction *visitInstruction(Instruction &I) { return nullptr; }
183 /// True when DB dominates all uses of DI except UI.
184 /// UI must be in the same block as DI.
185 /// The routine checks that the DI parent and DB are different.
186 bool dominatesAllUses(const Instruction *DI, const Instruction *UI,
187 const BasicBlock *DB) const;
189 /// Try to replace select with select operand SIOpd in SI-ICmp sequence.
190 bool replacedSelectWithOperand(SelectInst *SI, const ICmpInst *Icmp,
191 const unsigned SIOpd);
193 LoadInst *combineLoadToNewType(LoadInst &LI, Type *NewTy,
194 const Twine &Suffix = "");
197 bool annotateAnyAllocSite(CallBase &Call, const TargetLibraryInfo *TLI);
198 bool isDesirableIntType(unsigned BitWidth) const;
199 bool shouldChangeType(unsigned FromBitWidth, unsigned ToBitWidth) const;
200 bool shouldChangeType(Type *From, Type *To) const;
201 Value *dyn_castNegVal(Value *V) const;
203 /// Classify whether a cast is worth optimizing.
205 /// This is a helper to decide whether the simplification of
206 /// logic(cast(A), cast(B)) to cast(logic(A, B)) should be performed.
208 /// \param CI The cast we are interested in.
210 /// \return true if this cast actually results in any code being generated and
211 /// if it cannot already be eliminated by some other transformation.
212 bool shouldOptimizeCast(CastInst *CI);
214 /// Try to optimize a sequence of instructions checking if an operation
215 /// on LHS and RHS overflows.
217 /// If this overflow check is done via one of the overflow check intrinsics,
218 /// then CtxI has to be the call instruction calling that intrinsic. If this
219 /// overflow check is done by arithmetic followed by a compare, then CtxI has
220 /// to be the arithmetic instruction.
222 /// If a simplification is possible, stores the simplified result of the
223 /// operation in OperationResult and result of the overflow check in
224 /// OverflowResult, and return true. If no simplification is possible,
226 bool OptimizeOverflowCheck(Instruction::BinaryOps BinaryOp, bool IsSigned,
227 Value *LHS, Value *RHS,
228 Instruction &CtxI, Value *&OperationResult,
229 Constant *&OverflowResult);
231 Instruction *visitCallBase(CallBase &Call);
232 Instruction *tryOptimizeCall(CallInst *CI);
233 bool transformConstExprCastCall(CallBase &Call);
234 Instruction *transformCallThroughTrampoline(CallBase &Call,
235 IntrinsicInst &Tramp);
237 Value *simplifyMaskedLoad(IntrinsicInst &II);
238 Instruction *simplifyMaskedStore(IntrinsicInst &II);
239 Instruction *simplifyMaskedGather(IntrinsicInst &II);
240 Instruction *simplifyMaskedScatter(IntrinsicInst &II);
242 /// Transform (zext icmp) to bitwise / integer operations in order to
245 /// \param ICI The icmp of the (zext icmp) pair we are interested in.
246 /// \parem CI The zext of the (zext icmp) pair we are interested in.
248 /// \return null if the transformation cannot be performed. If the
249 /// transformation can be performed the new instruction that replaces the
250 /// (zext icmp) pair will be returned.
251 Instruction *transformZExtICmp(ICmpInst *Cmp, ZExtInst &Zext);
253 Instruction *transformSExtICmp(ICmpInst *Cmp, SExtInst &Sext);
255 bool willNotOverflowSignedAdd(const Value *LHS, const Value *RHS,
256 const Instruction &CxtI) const {
257 return computeOverflowForSignedAdd(LHS, RHS, &CxtI) ==
258 OverflowResult::NeverOverflows;
261 bool willNotOverflowUnsignedAdd(const Value *LHS, const Value *RHS,
262 const Instruction &CxtI) const {
263 return computeOverflowForUnsignedAdd(LHS, RHS, &CxtI) ==
264 OverflowResult::NeverOverflows;
267 bool willNotOverflowAdd(const Value *LHS, const Value *RHS,
268 const Instruction &CxtI, bool IsSigned) const {
269 return IsSigned ? willNotOverflowSignedAdd(LHS, RHS, CxtI)
270 : willNotOverflowUnsignedAdd(LHS, RHS, CxtI);
273 bool willNotOverflowSignedSub(const Value *LHS, const Value *RHS,
274 const Instruction &CxtI) const {
275 return computeOverflowForSignedSub(LHS, RHS, &CxtI) ==
276 OverflowResult::NeverOverflows;
279 bool willNotOverflowUnsignedSub(const Value *LHS, const Value *RHS,
280 const Instruction &CxtI) const {
281 return computeOverflowForUnsignedSub(LHS, RHS, &CxtI) ==
282 OverflowResult::NeverOverflows;
285 bool willNotOverflowSub(const Value *LHS, const Value *RHS,
286 const Instruction &CxtI, bool IsSigned) const {
287 return IsSigned ? willNotOverflowSignedSub(LHS, RHS, CxtI)
288 : willNotOverflowUnsignedSub(LHS, RHS, CxtI);
291 bool willNotOverflowSignedMul(const Value *LHS, const Value *RHS,
292 const Instruction &CxtI) const {
293 return computeOverflowForSignedMul(LHS, RHS, &CxtI) ==
294 OverflowResult::NeverOverflows;
297 bool willNotOverflowUnsignedMul(const Value *LHS, const Value *RHS,
298 const Instruction &CxtI) const {
299 return computeOverflowForUnsignedMul(LHS, RHS, &CxtI) ==
300 OverflowResult::NeverOverflows;
303 bool willNotOverflowMul(const Value *LHS, const Value *RHS,
304 const Instruction &CxtI, bool IsSigned) const {
305 return IsSigned ? willNotOverflowSignedMul(LHS, RHS, CxtI)
306 : willNotOverflowUnsignedMul(LHS, RHS, CxtI);
309 bool willNotOverflow(BinaryOperator::BinaryOps Opcode, const Value *LHS,
310 const Value *RHS, const Instruction &CxtI,
311 bool IsSigned) const {
313 case Instruction::Add: return willNotOverflowAdd(LHS, RHS, CxtI, IsSigned);
314 case Instruction::Sub: return willNotOverflowSub(LHS, RHS, CxtI, IsSigned);
315 case Instruction::Mul: return willNotOverflowMul(LHS, RHS, CxtI, IsSigned);
316 default: llvm_unreachable("Unexpected opcode for overflow query");
320 Value *EmitGEPOffset(User *GEP);
321 Instruction *scalarizePHI(ExtractElementInst &EI, PHINode *PN);
322 Instruction *foldBitcastExtElt(ExtractElementInst &ExtElt);
323 Instruction *foldCastedBitwiseLogic(BinaryOperator &I);
324 Instruction *foldBinopOfSextBoolToSelect(BinaryOperator &I);
325 Instruction *narrowBinOp(TruncInst &Trunc);
326 Instruction *narrowMaskedBinOp(BinaryOperator &And);
327 Instruction *narrowMathIfNoOverflow(BinaryOperator &I);
328 Instruction *narrowFunnelShift(TruncInst &Trunc);
329 Instruction *optimizeBitCastFromPhi(CastInst &CI, PHINode *PN);
330 Instruction *matchSAddSubSat(IntrinsicInst &MinMax1);
331 Instruction *foldNot(BinaryOperator &I);
332 Instruction *foldBinOpOfDisplacedShifts(BinaryOperator &I);
334 /// Determine if a pair of casts can be replaced by a single cast.
336 /// \param CI1 The first of a pair of casts.
337 /// \param CI2 The second of a pair of casts.
339 /// \return 0 if the cast pair cannot be eliminated, otherwise returns an
340 /// Instruction::CastOps value for a cast that can replace the pair, casting
341 /// CI1->getSrcTy() to CI2->getDstTy().
343 /// \see CastInst::isEliminableCastPair
344 Instruction::CastOps isEliminableCastPair(const CastInst *CI1,
345 const CastInst *CI2);
346 Value *simplifyIntToPtrRoundTripCast(Value *Val);
348 Value *foldAndOrOfICmps(ICmpInst *LHS, ICmpInst *RHS, Instruction &I,
349 bool IsAnd, bool IsLogical = false);
350 Value *foldXorOfICmps(ICmpInst *LHS, ICmpInst *RHS, BinaryOperator &Xor);
352 Value *foldEqOfParts(ICmpInst *Cmp0, ICmpInst *Cmp1, bool IsAnd);
354 Value *foldAndOrOfICmpsUsingRanges(ICmpInst *ICmp1, ICmpInst *ICmp2,
357 /// Optimize (fcmp)&(fcmp) or (fcmp)|(fcmp).
358 /// NOTE: Unlike most of instcombine, this returns a Value which should
359 /// already be inserted into the function.
360 Value *foldLogicOfFCmps(FCmpInst *LHS, FCmpInst *RHS, bool IsAnd,
361 bool IsLogicalSelect = false);
363 Instruction *foldLogicOfIsFPClass(BinaryOperator &Operator, Value *LHS,
367 canonicalizeConditionalNegationViaMathToSelect(BinaryOperator &i);
369 Value *foldAndOrOfICmpsOfAndWithPow2(ICmpInst *LHS, ICmpInst *RHS,
370 Instruction *CxtI, bool IsAnd,
371 bool IsLogical = false);
372 Value *matchSelectFromAndOr(Value *A, Value *B, Value *C, Value *D,
373 bool InvertFalseVal = false);
374 Value *getSelectCondition(Value *A, Value *B, bool ABIsTheSame);
376 Instruction *foldLShrOverflowBit(BinaryOperator &I);
377 Instruction *foldExtractOfOverflowIntrinsic(ExtractValueInst &EV);
378 Instruction *foldIntrinsicWithOverflowCommon(IntrinsicInst *II);
379 Instruction *foldIntrinsicIsFPClass(IntrinsicInst &II);
380 Instruction *foldFPSignBitOps(BinaryOperator &I);
381 Instruction *foldFDivConstantDivisor(BinaryOperator &I);
383 // Optimize one of these forms:
384 // and i1 Op, SI / select i1 Op, i1 SI, i1 false (if IsAnd = true)
385 // or i1 Op, SI / select i1 Op, i1 true, i1 SI (if IsAnd = false)
386 // into simplier select instruction using isImpliedCondition.
387 Instruction *foldAndOrOfSelectUsingImpliedCond(Value *Op, SelectInst &SI,
391 /// Create and insert the idiom we use to indicate a block is unreachable
392 /// without having to rewrite the CFG from within InstCombine.
393 void CreateNonTerminatorUnreachable(Instruction *InsertAt) {
394 auto &Ctx = InsertAt->getContext();
395 auto *SI = new StoreInst(ConstantInt::getTrue(Ctx),
396 PoisonValue::get(Type::getInt1PtrTy(Ctx)),
397 /*isVolatile*/ false, Align(1));
398 InsertNewInstBefore(SI, *InsertAt);
401 /// Combiner aware instruction erasure.
403 /// When dealing with an instruction that has side effects or produces a void
404 /// value, we can't rely on DCE to delete the instruction. Instead, visit
405 /// methods should return the value returned by this function.
406 Instruction *eraseInstFromFunction(Instruction &I) override {
407 LLVM_DEBUG(dbgs() << "IC: ERASE " << I << '\n');
408 assert(I.use_empty() && "Cannot erase instruction that is used!");
411 // Make sure that we reprocess all operands now that we reduced their
413 SmallVector<Value *> Ops(I.operands());
416 for (Value *Op : Ops)
417 Worklist.handleUseCountDecrement(Op);
419 return nullptr; // Don't do anything with FI
422 OverflowResult computeOverflow(
423 Instruction::BinaryOps BinaryOp, bool IsSigned,
424 Value *LHS, Value *RHS, Instruction *CxtI) const;
426 /// Performs a few simplifications for operators which are associative
428 bool SimplifyAssociativeOrCommutative(BinaryOperator &I);
430 /// Tries to simplify binary operations which some other binary
431 /// operation distributes over.
433 /// It does this by either by factorizing out common terms (eg "(A*B)+(A*C)"
434 /// -> "A*(B+C)") or expanding out if this results in simplifications (eg: "A
435 /// & (B | C) -> (A&B) | (A&C)" if this is a win). Returns the simplified
436 /// value, or null if it didn't simplify.
437 Value *foldUsingDistributiveLaws(BinaryOperator &I);
439 /// Tries to simplify add operations using the definition of remainder.
441 /// The definition of remainder is X % C = X - (X / C ) * C. The add
442 /// expression X % C0 + (( X / C0 ) % C1) * C0 can be simplified to
444 Value *SimplifyAddWithRemainder(BinaryOperator &I);
446 // Binary Op helper for select operations where the expression can be
447 // efficiently reorganized.
448 Value *SimplifySelectsFeedingBinaryOp(BinaryOperator &I, Value *LHS,
451 // (Binop1 (Binop2 (logic_shift X, C), C1), (logic_shift Y, C))
452 // -> (logic_shift (Binop1 (Binop2 X, inv_logic_shift(C1, C)), Y), C)
453 // (Binop1 (Binop2 (logic_shift X, Amt), Mask), (logic_shift Y, Amt))
454 // -> (BinOp (logic_shift (BinOp X, Y)), Mask)
455 Instruction *foldBinOpShiftWithShift(BinaryOperator &I);
457 /// Tries to simplify binops of select and cast of the select condition.
459 /// (Binop (cast C), (select C, T, F))
460 /// -> (select C, C0, C1)
461 Instruction *foldBinOpOfSelectAndCastOfSelectCondition(BinaryOperator &I);
463 /// This tries to simplify binary operations by factorizing out common terms
464 /// (e. g. "(A*B)+(A*C)" -> "A*(B+C)").
465 Value *tryFactorizationFolds(BinaryOperator &I);
467 /// Match a select chain which produces one of three values based on whether
468 /// the LHS is less than, equal to, or greater than RHS respectively.
469 /// Return true if we matched a three way compare idiom. The LHS, RHS, Less,
470 /// Equal and Greater values are saved in the matching process and returned to
472 bool matchThreeWayIntCompare(SelectInst *SI, Value *&LHS, Value *&RHS,
473 ConstantInt *&Less, ConstantInt *&Equal,
474 ConstantInt *&Greater);
476 /// Attempts to replace V with a simpler value based on the demanded
478 Value *SimplifyDemandedUseBits(Value *V, APInt DemandedMask, KnownBits &Known,
479 unsigned Depth, Instruction *CxtI);
480 bool SimplifyDemandedBits(Instruction *I, unsigned Op,
481 const APInt &DemandedMask, KnownBits &Known,
482 unsigned Depth = 0) override;
484 /// Helper routine of SimplifyDemandedUseBits. It computes KnownZero/KnownOne
485 /// bits. It also tries to handle simplifications that can be done based on
486 /// DemandedMask, but without modifying the Instruction.
487 Value *SimplifyMultipleUseDemandedBits(Instruction *I,
488 const APInt &DemandedMask,
490 unsigned Depth, Instruction *CxtI);
492 /// Helper routine of SimplifyDemandedUseBits. It tries to simplify demanded
493 /// bit for "r1 = shr x, c1; r2 = shl r1, c2" instruction sequence.
494 Value *simplifyShrShlDemandedBits(
495 Instruction *Shr, const APInt &ShrOp1, Instruction *Shl,
496 const APInt &ShlOp1, const APInt &DemandedMask, KnownBits &Known);
498 /// Tries to simplify operands to an integer instruction based on its
500 bool SimplifyDemandedInstructionBits(Instruction &Inst);
502 Value *SimplifyDemandedVectorElts(Value *V, APInt DemandedElts,
503 APInt &UndefElts, unsigned Depth = 0,
504 bool AllowMultipleUsers = false) override;
506 /// Canonicalize the position of binops relative to shufflevector.
507 Instruction *foldVectorBinop(BinaryOperator &Inst);
508 Instruction *foldVectorSelect(SelectInst &Sel);
509 Instruction *foldSelectShuffle(ShuffleVectorInst &Shuf);
511 /// Given a binary operator, cast instruction, or select which has a PHI node
512 /// as operand #0, see if we can fold the instruction into the PHI (which is
513 /// only possible if all operands to the PHI are constants).
514 Instruction *foldOpIntoPhi(Instruction &I, PHINode *PN);
516 /// For a binary operator with 2 phi operands, try to hoist the binary
517 /// operation before the phi. This can result in fewer instructions in
518 /// patterns where at least one set of phi operands simplifies.
520 /// BB3: binop (phi [X, BB1], [C1, BB2]), (phi [Y, BB1], [C2, BB2])
522 /// BB1: BO = binop X, Y
523 /// BB3: phi [BO, BB1], [(binop C1, C2), BB2]
524 Instruction *foldBinopWithPhiOperands(BinaryOperator &BO);
526 /// Given an instruction with a select as one operand and a constant as the
527 /// other operand, try to fold the binary operator into the select arguments.
528 /// This also works for Cast instructions, which obviously do not have a
530 Instruction *FoldOpIntoSelect(Instruction &Op, SelectInst *SI,
531 bool FoldWithMultiUse = false);
533 /// This is a convenience wrapper function for the above two functions.
534 Instruction *foldBinOpIntoSelectOrPhi(BinaryOperator &I);
536 Instruction *foldAddWithConstant(BinaryOperator &Add);
538 /// Try to rotate an operation below a PHI node, using PHI nodes for
540 Instruction *foldPHIArgOpIntoPHI(PHINode &PN);
541 Instruction *foldPHIArgBinOpIntoPHI(PHINode &PN);
542 Instruction *foldPHIArgInsertValueInstructionIntoPHI(PHINode &PN);
543 Instruction *foldPHIArgExtractValueInstructionIntoPHI(PHINode &PN);
544 Instruction *foldPHIArgGEPIntoPHI(PHINode &PN);
545 Instruction *foldPHIArgLoadIntoPHI(PHINode &PN);
546 Instruction *foldPHIArgZextsIntoPHI(PHINode &PN);
547 Instruction *foldPHIArgIntToPtrToPHI(PHINode &PN);
549 /// If an integer typed PHI has only one use which is an IntToPtr operation,
550 /// replace the PHI with an existing pointer typed PHI if it exists. Otherwise
551 /// insert a new pointer typed PHI and replace the original one.
552 bool foldIntegerTypedPHI(PHINode &PN);
554 /// Helper function for FoldPHIArgXIntoPHI() to set debug location for the
555 /// folded operation.
556 void PHIArgMergedDebugLoc(Instruction *Inst, PHINode &PN);
558 Instruction *foldGEPICmp(GEPOperator *GEPLHS, Value *RHS,
559 ICmpInst::Predicate Cond, Instruction &I);
560 Instruction *foldSelectICmp(ICmpInst::Predicate Pred, SelectInst *SI,
561 Value *RHS, const ICmpInst &I);
562 bool foldAllocaCmp(AllocaInst *Alloca);
563 Instruction *foldCmpLoadFromIndexedGlobal(LoadInst *LI,
564 GetElementPtrInst *GEP,
565 GlobalVariable *GV, CmpInst &ICI,
566 ConstantInt *AndCst = nullptr);
567 Instruction *foldFCmpIntToFPConst(FCmpInst &I, Instruction *LHSI,
569 Instruction *foldICmpAddOpConst(Value *X, const APInt &C,
570 ICmpInst::Predicate Pred);
571 Instruction *foldICmpWithCastOp(ICmpInst &ICmp);
572 Instruction *foldICmpWithZextOrSext(ICmpInst &ICmp);
574 Instruction *foldICmpUsingKnownBits(ICmpInst &Cmp);
575 Instruction *foldICmpWithDominatingICmp(ICmpInst &Cmp);
576 Instruction *foldICmpWithConstant(ICmpInst &Cmp);
577 Instruction *foldICmpUsingBoolRange(ICmpInst &I);
578 Instruction *foldICmpInstWithConstant(ICmpInst &Cmp);
579 Instruction *foldICmpInstWithConstantNotInt(ICmpInst &Cmp);
580 Instruction *foldICmpInstWithConstantAllowUndef(ICmpInst &Cmp,
582 Instruction *foldICmpBinOp(ICmpInst &Cmp, const SimplifyQuery &SQ);
583 Instruction *foldICmpEquality(ICmpInst &Cmp);
584 Instruction *foldIRemByPowerOfTwoToBitTest(ICmpInst &I);
585 Instruction *foldSignBitTest(ICmpInst &I);
586 Instruction *foldICmpWithZero(ICmpInst &Cmp);
588 Value *foldMultiplicationOverflowCheck(ICmpInst &Cmp);
590 Instruction *foldICmpBinOpWithConstant(ICmpInst &Cmp, BinaryOperator *BO,
592 Instruction *foldICmpSelectConstant(ICmpInst &Cmp, SelectInst *Select,
594 Instruction *foldICmpTruncConstant(ICmpInst &Cmp, TruncInst *Trunc,
596 Instruction *foldICmpAndConstant(ICmpInst &Cmp, BinaryOperator *And,
598 Instruction *foldICmpXorConstant(ICmpInst &Cmp, BinaryOperator *Xor,
600 Instruction *foldICmpOrConstant(ICmpInst &Cmp, BinaryOperator *Or,
602 Instruction *foldICmpMulConstant(ICmpInst &Cmp, BinaryOperator *Mul,
604 Instruction *foldICmpShlConstant(ICmpInst &Cmp, BinaryOperator *Shl,
606 Instruction *foldICmpShrConstant(ICmpInst &Cmp, BinaryOperator *Shr,
608 Instruction *foldICmpSRemConstant(ICmpInst &Cmp, BinaryOperator *UDiv,
610 Instruction *foldICmpUDivConstant(ICmpInst &Cmp, BinaryOperator *UDiv,
612 Instruction *foldICmpDivConstant(ICmpInst &Cmp, BinaryOperator *Div,
614 Instruction *foldICmpSubConstant(ICmpInst &Cmp, BinaryOperator *Sub,
616 Instruction *foldICmpAddConstant(ICmpInst &Cmp, BinaryOperator *Add,
618 Instruction *foldICmpAndConstConst(ICmpInst &Cmp, BinaryOperator *And,
620 Instruction *foldICmpAndShift(ICmpInst &Cmp, BinaryOperator *And,
621 const APInt &C1, const APInt &C2);
622 Instruction *foldICmpXorShiftConst(ICmpInst &Cmp, BinaryOperator *Xor,
624 Instruction *foldICmpShrConstConst(ICmpInst &I, Value *ShAmt, const APInt &C1,
626 Instruction *foldICmpShlConstConst(ICmpInst &I, Value *ShAmt, const APInt &C1,
629 Instruction *foldICmpBinOpEqualityWithConstant(ICmpInst &Cmp,
632 Instruction *foldICmpIntrinsicWithConstant(ICmpInst &ICI, IntrinsicInst *II,
634 Instruction *foldICmpEqIntrinsicWithConstant(ICmpInst &ICI, IntrinsicInst *II,
636 Instruction *foldICmpBitCast(ICmpInst &Cmp);
637 Instruction *foldICmpWithTrunc(ICmpInst &Cmp);
639 // Helpers of visitSelectInst().
640 Instruction *foldSelectOfBools(SelectInst &SI);
641 Instruction *foldSelectExtConst(SelectInst &Sel);
642 Instruction *foldSelectOpOp(SelectInst &SI, Instruction *TI, Instruction *FI);
643 Instruction *foldSelectIntoOp(SelectInst &SI, Value *, Value *);
644 Instruction *foldSPFofSPF(Instruction *Inner, SelectPatternFlavor SPF1,
645 Value *A, Value *B, Instruction &Outer,
646 SelectPatternFlavor SPF2, Value *C);
647 Instruction *foldSelectInstWithICmp(SelectInst &SI, ICmpInst *ICI);
648 Instruction *foldSelectValueEquivalence(SelectInst &SI, ICmpInst &ICI);
649 bool replaceInInstruction(Value *V, Value *Old, Value *New,
652 Value *insertRangeTest(Value *V, const APInt &Lo, const APInt &Hi,
653 bool isSigned, bool Inside);
654 bool mergeStoreIntoSuccessor(StoreInst &SI);
656 /// Given an initial instruction, check to see if it is the root of a
657 /// bswap/bitreverse idiom. If so, return the equivalent bswap/bitreverse
659 Instruction *matchBSwapOrBitReverse(Instruction &I, bool MatchBSwaps,
660 bool MatchBitReversals);
662 Instruction *SimplifyAnyMemTransfer(AnyMemTransferInst *MI);
663 Instruction *SimplifyAnyMemSet(AnyMemSetInst *MI);
665 Value *EvaluateInDifferentType(Value *V, Type *Ty, bool isSigned);
667 bool tryToSinkInstruction(Instruction *I, BasicBlock *DestBlock);
669 bool removeInstructionsBeforeUnreachable(Instruction &I);
670 bool handleUnreachableFrom(Instruction *I);
671 bool handlePotentiallyDeadSuccessors(BasicBlock *BB, BasicBlock *LiveSucc);
672 void freelyInvertAllUsersOf(Value *V, Value *IgnoredUser = nullptr);
675 class Negator final {
676 /// Top-to-bottom, def-to-use negated instruction tree we produced.
677 SmallVector<Instruction *, NegatorMaxNodesSSO> NewInstructions;
679 using BuilderTy = IRBuilder<TargetFolder, IRBuilderCallbackInserter>;
682 const DataLayout &DL;
684 const DominatorTree &DT;
686 const bool IsTrulyNegation;
688 SmallDenseMap<Value *, Value *> NegationsCache;
690 Negator(LLVMContext &C, const DataLayout &DL, AssumptionCache &AC,
691 const DominatorTree &DT, bool IsTrulyNegation);
693 #if LLVM_ENABLE_STATS
694 unsigned NumValuesVisitedInThisNegator = 0;
698 using Result = std::pair<ArrayRef<Instruction *> /*NewInstructions*/,
699 Value * /*NegatedRoot*/>;
701 std::array<Value *, 2> getSortedOperandsOfBinOp(Instruction *I);
703 [[nodiscard]] Value *visitImpl(Value *V, unsigned Depth);
705 [[nodiscard]] Value *negate(Value *V, unsigned Depth);
707 /// Recurse depth-first and attempt to sink the negation.
708 /// FIXME: use worklist?
709 [[nodiscard]] std::optional<Result> run(Value *Root);
711 Negator(const Negator &) = delete;
712 Negator(Negator &&) = delete;
713 Negator &operator=(const Negator &) = delete;
714 Negator &operator=(Negator &&) = delete;
717 /// Attempt to negate \p Root. Retuns nullptr if negation can't be performed,
718 /// otherwise returns negated value.
719 [[nodiscard]] static Value *Negate(bool LHSIsZero, Value *Root,
720 InstCombinerImpl &IC);
723 } // end namespace llvm
727 #endif // LLVM_LIB_TRANSFORMS_INSTCOMBINE_INSTCOMBINEINTERNAL_H