1//===- InstCombineInternal.h - InstCombine pass internals -------*- C++ -*-===//
2//
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
6//
7//===----------------------------------------------------------------------===//
8//
9/// \file
10///
11/// This file provides internal interfaces used to implement the InstCombine.
12//
13//===----------------------------------------------------------------------===//
14
15#ifndef LLVM_LIB_TRANSFORMS_INSTCOMBINE_INSTCOMBINEINTERNAL_H
16#define LLVM_LIB_TRANSFORMS_INSTCOMBINE_INSTCOMBINEINTERNAL_H
17
18#include "InstCombineCLOptions.h"
19#include "llvm/ADT/PostOrderIterator.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/IRBuilder.h"
25#include "llvm/IR/InstVisitor.h"
26#include "llvm/IR/PatternMatch.h"
27#include "llvm/IR/ProfDataUtils.h"
28#include "llvm/IR/Value.h"
29#include "llvm/Support/Debug.h"
30#include "llvm/Support/KnownBits.h"
31#include "llvm/Support/KnownFPClass.h"
32#include "llvm/Transforms/InstCombine/InstCombiner.h"
33#include "llvm/Transforms/Utils/Local.h"
34#include <cassert>
35
36#define DEBUG_TYPE "instcombine"
37#include "llvm/Transforms/Utils/InstructionWorklist.h"
38
39// Let's guesstimate that most often we will end up visiting/producing
40// fairly small number of new instructions.
41static constexpr unsigned NegatorMaxNodesSSO = 16;
42
43namespace llvm {
44
45class AAResults;
46class APInt;
47class AssumptionCache;
48class BlockFrequencyInfo;
49class DataLayout;
50class DominatorTree;
51class GEPOperator;
52class GlobalVariable;
53class OptimizationRemarkEmitter;
54class ProfileSummaryInfo;
55class TargetLibraryInfo;
56class User;
57
58/// Enum to specify how shift operations should be evaluated in
59/// canEvaluateShifted.
60/// Lossy: Allows lossy transformations
61/// Signed: Requires lossless transformation, using ashr to restore for shl,
62/// or represents ashr handling for right shifts
63/// Unsigned: Requires lossless transformation, using lshr to restore for shl,
64/// or represents lshr handling for right shifts
65enum class ShiftSemantics { Lossy, Signed, Unsigned };
66
67class LLVM_LIBRARY_VISIBILITY InstCombinerImpl final
68 : public InstCombiner,
69 public InstVisitor<InstCombinerImpl, Instruction *> {
70public:
71 InstCombinerImpl(InstructionWorklist &Worklist, Function &F, AAResults *AA,
72 AssumptionCache &AC, TargetLibraryInfo &TLI,
73 TargetTransformInfo &TTI, DominatorTree &DT,
74 OptimizationRemarkEmitter &ORE, BlockFrequencyInfo *BFI,
75 BranchProbabilityInfo *BPI, ProfileSummaryInfo *PSI,
76 const DataLayout &DL,
77 ReversePostOrderTraversal<BasicBlock *> &RPOT,
78 const InstCombineCLOptions &CLOpts)
79 : InstCombiner(Worklist, F, AA, AC, TLI, TTI, DT, ORE, BFI, BPI, PSI, DL,
80 RPOT),
81 CLOpts(CLOpts) {}
82
83 ~InstCombinerImpl() override = default;
84
85 const InstCombineCLOptions &CLOpts;
86
87 /// Perform early cleanup and prepare the InstCombine worklist.
88 bool prepareWorklist(Function &F);
89
90 /// Run the combiner over the entire worklist until it is empty.
91 ///
92 /// \returns true if the IR is changed.
93 bool run();
94
95 // Visitation implementation - Implement instruction combining for different
96 // instruction types. The semantics are as follows:
97 // Return Value:
98 // null - No change was made
99 // I - Change was made, I is still valid, I may be dead though
100 // otherwise - Change was made, replace I with returned instruction
101 //
102 Instruction *visitFNeg(UnaryOperator &I);
103 Instruction *visitAdd(BinaryOperator &I);
104 Instruction *visitFAdd(BinaryOperator &I);
105 Value *OptimizePointerDifference(
106 Value *LHS, Value *RHS, Type *Ty, bool isNUW);
107 Instruction *visitSub(BinaryOperator &I);
108 Instruction *visitFSub(BinaryOperator &I);
109 Instruction *visitMul(BinaryOperator &I);
110 Instruction *foldPowiReassoc(BinaryOperator &I);
111 Instruction *foldFMulReassoc(BinaryOperator &I);
112 Instruction *visitFMul(BinaryOperator &I);
113 Instruction *visitURem(BinaryOperator &I);
114 Instruction *visitSRem(BinaryOperator &I);
115 Instruction *visitFRem(BinaryOperator &I);
116 bool simplifyDivRemOfSelectWithZeroOp(BinaryOperator &I);
117 Instruction *commonIDivRemTransforms(BinaryOperator &I);
118 Instruction *commonIRemTransforms(BinaryOperator &I);
119 Instruction *commonIDivTransforms(BinaryOperator &I);
120 Instruction *visitUDiv(BinaryOperator &I);
121 Instruction *visitSDiv(BinaryOperator &I);
122 Instruction *visitFDiv(BinaryOperator &I);
123 Value *simplifyRangeCheck(CmpPredicate PredL, Value *LHS0, Value *LHS1,
124 CmpPredicate PredR, Value *RHS0, Value *RHS1,
125 Instruction *CtxI, bool Inverted);
126 Instruction *FoldOrOfLogicalAnds(Value *Op0, Value *Op1);
127 Instruction *visitAnd(BinaryOperator &I);
128 Instruction *visitOr(BinaryOperator &I);
129 bool sinkNotIntoLogicalOp(Instruction &I);
130 bool sinkNotIntoOtherHandOfLogicalOp(Instruction &I);
131 Instruction *visitXor(BinaryOperator &I);
132 Instruction *visitShl(BinaryOperator &I);
133 Value *reassociateShiftAmtsOfTwoSameDirectionShifts(
134 BinaryOperator *Sh0, const SimplifyQuery &SQ,
135 bool AnalyzeForSignBitExtraction = false);
136 Instruction *canonicalizeCondSignextOfHighBitExtractToSignextHighBitExtract(
137 BinaryOperator &I);
138 Instruction *foldVariableSignZeroExtensionOfVariableHighBitExtract(
139 BinaryOperator &OldAShr);
140 Instruction *visitAShr(BinaryOperator &I);
141 Instruction *visitLShr(BinaryOperator &I);
142 Instruction *commonShiftTransforms(BinaryOperator &I);
143 Instruction *visitFCmpInst(FCmpInst &I);
144 CmpInst *canonicalizeICmpPredicate(CmpInst &I);
145 Instruction *visitICmpInst(ICmpInst &I);
146 Instruction *FoldShiftByConstant(Value *Op0, Constant *Op1,
147 BinaryOperator &I);
148 Instruction *commonCastTransforms(CastInst &CI);
149 Instruction *visitTrunc(TruncInst &CI);
150 Instruction *visitZExt(ZExtInst &Zext);
151 Instruction *visitSExt(SExtInst &Sext);
152 Instruction *visitFPTrunc(FPTruncInst &CI);
153 Instruction *visitFPExt(CastInst &CI);
154 Instruction *visitFPToUI(FPToUIInst &FI);
155 Instruction *visitFPToSI(FPToSIInst &FI);
156 Instruction *visitUIToFP(CastInst &CI);
157 Instruction *visitSIToFP(CastInst &CI);
158 Instruction *visitPtrToInt(PtrToIntInst &CI);
159 Instruction *visitPtrToAddr(PtrToAddrInst &CI);
160 Instruction *visitIntToPtr(IntToPtrInst &CI);
161 Instruction *visitBitCast(BitCastInst &CI);
162 Instruction *visitAddrSpaceCast(AddrSpaceCastInst &CI);
163 template <typename FPToIntTy> Instruction *foldItoFPtoI(FPToIntTy &FI);
164 Instruction *visitSelectInst(SelectInst &SI);
165 Instruction *foldShuffledIntrinsicOperands(IntrinsicInst *II);
166 Value *foldReversedIntrinsicOperands(IntrinsicInst *II);
167 Instruction *visitCallInst(CallInst &CI);
168 Instruction *visitInvokeInst(InvokeInst &II);
169 Instruction *visitCallBrInst(CallBrInst &CBI);
170
171 Instruction *SliceUpIllegalIntegerPHI(PHINode &PN);
172 Instruction *visitPHINode(PHINode &PN);
173 Instruction *visitGetElementPtrInst(GetElementPtrInst &GEP);
174 Instruction *visitGEPOfGEP(GetElementPtrInst &GEP, GEPOperator *Src);
175 Instruction *visitAllocaInst(AllocaInst &AI);
176 Instruction *visitAllocSite(Instruction &FI);
177 Instruction *visitFree(CallInst &FI, Value *FreedOp);
178 Instruction *visitLoadInst(LoadInst &LI);
179 Instruction *visitStoreInst(StoreInst &SI);
180 Instruction *visitAtomicRMWInst(AtomicRMWInst &SI);
181 Instruction *visitUncondBrInst(UncondBrInst &BI);
182 Instruction *visitCondBrInst(CondBrInst &BI);
183 Instruction *visitFenceInst(FenceInst &FI);
184 Instruction *visitSwitchInst(SwitchInst &SI);
185 Instruction *visitReturnInst(ReturnInst &RI);
186 Instruction *visitUnreachableInst(UnreachableInst &I);
187 Instruction *
188 foldAggregateConstructionIntoAggregateReuse(InsertValueInst &OrigIVI);
189 Instruction *visitInsertValueInst(InsertValueInst &IV);
190 Instruction *visitInsertElementInst(InsertElementInst &IE);
191 Instruction *visitExtractElementInst(ExtractElementInst &EI);
192 Instruction *simplifyBinOpSplats(ShuffleVectorInst &SVI);
193 Instruction *visitShuffleVectorInst(ShuffleVectorInst &SVI);
194 Instruction *visitExtractValueInst(ExtractValueInst &EV);
195 Instruction *visitBitInsertInst(BitInsertInst &BI);
196 Instruction *visitBitExtractInst(BitExtractInst &BE);
197 Instruction *visitLandingPadInst(LandingPadInst &LI);
198 Instruction *visitVAEndInst(VAEndInst &I);
199 Value *pushFreezeToPreventPoisonFromPropagating(FreezeInst &FI);
200 bool freezeOtherUses(FreezeInst &FI);
201 Instruction *foldFreezeIntoRecurrence(FreezeInst &I, PHINode *PN);
202 Instruction *visitFreeze(FreezeInst &I);
203
204 /// Specify what to return for unhandled instructions.
205 Instruction *visitInstruction(Instruction &I) { return nullptr; }
206
207 /// True when DB dominates all uses of DI except UI.
208 /// UI must be in the same block as DI.
209 /// The routine checks that the DI parent and DB are different.
210 bool dominatesAllUses(const Instruction *DI, const Instruction *UI,
211 const BasicBlock *DB) const;
212
213 /// Try to replace select with select operand SIOpd in SI-ICmp sequence.
214 bool replacedSelectWithOperand(SelectInst *SI, const ICmpInst *Icmp,
215 const unsigned SIOpd);
216
217 LoadInst *combineLoadToNewType(LoadInst &LI, Type *NewTy,
218 const Twine &Suffix = "");
219
220 /// Check if fmul \p MulVal, +0.0 will yield +0.0 (or signed zero is
221 /// ignorable).
222 bool fmulByZeroIsZero(Value *MulVal, FastMathFlags FMF,
223 const Instruction *CtxI) const;
224
225 std::optional<std::pair<Intrinsic::ID, SmallVector<Value *, 3>>>
226 convertOrOfShiftsToFunnelShift(Instruction &Or);
227
228private:
229 bool annotateAnyAllocSite(CallBase &Call, const TargetLibraryInfo *TLI);
230 bool isDesirableIntType(unsigned BitWidth) const;
231 bool shouldChangeType(unsigned FromBitWidth, unsigned ToBitWidth) const;
232 bool shouldChangeType(Type *From, Type *To) const;
233 Value *dyn_castNegVal(Value *V) const;
234
235 /// Classify whether a cast is worth optimizing.
236 ///
237 /// This is a helper to decide whether the simplification of
238 /// logic(cast(A), cast(B)) to cast(logic(A, B)) should be performed.
239 ///
240 /// \param CI The cast we are interested in.
241 ///
242 /// \return true if this cast actually results in any code being generated and
243 /// if it cannot already be eliminated by some other transformation.
244 bool shouldOptimizeCast(CastInst *CI);
245
246 /// Try to optimize a sequence of instructions checking if an operation
247 /// on LHS and RHS overflows.
248 ///
249 /// If this overflow check is done via one of the overflow check intrinsics,
250 /// then CtxI has to be the call instruction calling that intrinsic. If this
251 /// overflow check is done by arithmetic followed by a compare, then CtxI has
252 /// to be the arithmetic instruction.
253 ///
254 /// If a simplification is possible, stores the simplified result of the
255 /// operation in OperationResult and result of the overflow check in
256 /// OverflowResult, and return true. If no simplification is possible,
257 /// returns false.
258 bool OptimizeOverflowCheck(Instruction::BinaryOps BinaryOp, bool IsSigned,
259 Value *LHS, Value *RHS,
260 Instruction &CtxI, Value *&OperationResult,
261 Constant *&OverflowResult);
262
263 Instruction *visitCallBase(CallBase &Call);
264 Instruction *tryOptimizeCall(CallInst *CI);
265 bool transformConstExprCastCall(CallBase &Call);
266 Instruction *transformCallThroughTrampoline(CallBase &Call,
267 IntrinsicInst &Tramp);
268
269 /// Try to optimize a call to the result of a ptrauth intrinsic, potentially
270 /// into the ptrauth call bundle:
271 /// - call(ptrauth.resign(p)), ["ptrauth"()] -> call p, ["ptrauth"()]
272 /// - call(ptrauth.sign(p)), ["ptrauth"()] -> call p
273 /// as long as the key/discriminator are the same in sign and auth-bundle,
274 /// and we don't change the key in the bundle (to a potentially-invalid key.)
275 Instruction *foldPtrAuthIntrinsicCallee(CallBase &Call);
276
277 /// Try to optimize a call to a ptrauth constant, into its ptrauth bundle:
278 /// call(ptrauth(f)), ["ptrauth"()] -> call f
279 /// as long as the key/discriminator are the same in constant and bundle.
280 Instruction *foldPtrAuthConstantCallee(CallBase &Call);
281
282 // Return (a, b) if (LHS, RHS) is known to be (a, b) or (b, a).
283 // Otherwise, return std::nullopt
284 // Currently it matches:
285 // - LHS = (select c, a, b), RHS = (select c, b, a)
286 // - LHS = (phi [a, BB0], [b, BB1]), RHS = (phi [b, BB0], [a, BB1])
287 // - LHS = min(a, b), RHS = max(a, b)
288 std::optional<std::pair<Value *, Value *>> matchSymmetricPair(Value *LHS,
289 Value *RHS);
290
291 Value *simplifyMaskedLoad(IntrinsicInst &II);
292 Instruction *simplifyMaskedStore(IntrinsicInst &II);
293 Instruction *simplifyMaskedGather(IntrinsicInst &II);
294 Instruction *simplifyMaskedScatter(IntrinsicInst &II);
295
296 /// Transform (zext icmp) to bitwise / integer operations in order to
297 /// eliminate it.
298 ///
299 /// \param ICI The icmp of the (zext icmp) pair we are interested in.
300 /// \parem CI The zext of the (zext icmp) pair we are interested in.
301 ///
302 /// \return null if the transformation cannot be performed. If the
303 /// transformation can be performed the new instruction that replaces the
304 /// (zext icmp) pair will be returned.
305 Instruction *transformZExtICmp(ICmpInst *Cmp, ZExtInst &Zext);
306
307 Instruction *transformSExtICmp(ICmpInst *Cmp, SExtInst &Sext);
308
309 bool willNotOverflowSignedAdd(const WithCache<const Value *> &LHS,
310 const WithCache<const Value *> &RHS,
311 const Instruction &CtxI) const {
312 return computeOverflowForSignedAdd(LHS, RHS, CtxI: &CtxI) ==
313 OverflowResult::NeverOverflows;
314 }
315
316 bool willNotOverflowUnsignedAdd(const WithCache<const Value *> &LHS,
317 const WithCache<const Value *> &RHS,
318 const Instruction &CtxI) const {
319 return computeOverflowForUnsignedAdd(LHS, RHS, CtxI: &CtxI) ==
320 OverflowResult::NeverOverflows;
321 }
322
323 bool willNotOverflowAdd(const Value *LHS, const Value *RHS,
324 const Instruction &CtxI, bool IsSigned) const {
325 return IsSigned ? willNotOverflowSignedAdd(LHS, RHS, CtxI)
326 : willNotOverflowUnsignedAdd(LHS, RHS, CtxI);
327 }
328
329 bool willNotOverflowSignedSub(const Value *LHS, const Value *RHS,
330 const Instruction &CtxI) const {
331 return computeOverflowForSignedSub(LHS, RHS, CtxI: &CtxI) ==
332 OverflowResult::NeverOverflows;
333 }
334
335 bool willNotOverflowUnsignedSub(const Value *LHS, const Value *RHS,
336 const Instruction &CtxI) const {
337 return computeOverflowForUnsignedSub(LHS, RHS, CtxI: &CtxI) ==
338 OverflowResult::NeverOverflows;
339 }
340
341 bool willNotOverflowSub(const Value *LHS, const Value *RHS,
342 const Instruction &CtxI, bool IsSigned) const {
343 return IsSigned ? willNotOverflowSignedSub(LHS, RHS, CtxI)
344 : willNotOverflowUnsignedSub(LHS, RHS, CtxI);
345 }
346
347 bool willNotOverflowSignedMul(const Value *LHS, const Value *RHS,
348 const Instruction &CtxI) const {
349 return computeOverflowForSignedMul(LHS, RHS, CtxI: &CtxI) ==
350 OverflowResult::NeverOverflows;
351 }
352
353 bool willNotOverflowUnsignedMul(const Value *LHS, const Value *RHS,
354 const Instruction &CtxI,
355 bool IsNSW = false) const {
356 return computeOverflowForUnsignedMul(LHS, RHS, CtxI: &CtxI, IsNSW) ==
357 OverflowResult::NeverOverflows;
358 }
359
360 bool willNotOverflowMul(const Value *LHS, const Value *RHS,
361 const Instruction &CtxI, bool IsSigned) const {
362 return IsSigned ? willNotOverflowSignedMul(LHS, RHS, CtxI)
363 : willNotOverflowUnsignedMul(LHS, RHS, CtxI);
364 }
365
366 bool willNotOverflow(BinaryOperator::BinaryOps Opcode, const Value *LHS,
367 const Value *RHS, const Instruction &CtxI,
368 bool IsSigned) const {
369 switch (Opcode) {
370 case Instruction::Add: return willNotOverflowAdd(LHS, RHS, CtxI, IsSigned);
371 case Instruction::Sub: return willNotOverflowSub(LHS, RHS, CtxI, IsSigned);
372 case Instruction::Mul: return willNotOverflowMul(LHS, RHS, CtxI, IsSigned);
373 default: llvm_unreachable("Unexpected opcode for overflow query");
374 }
375 }
376
377 Value *EmitGEPOffset(GEPOperator *GEP, bool RewriteGEP = false);
378 /// Emit sum of multiple GEP offsets. The GEPs are processed in reverse
379 /// order.
380 Value *EmitGEPOffsets(ArrayRef<GEPOperator *> GEPs, GEPNoWrapFlags NW,
381 Type *IdxTy, bool RewriteGEPs);
382 Instruction *scalarizePHI(ExtractElementInst &EI, PHINode *PN);
383 Instruction *foldBitcastExtElt(ExtractElementInst &ExtElt);
384 Instruction *foldCastedBitwiseLogic(BinaryOperator &I);
385 Instruction *foldFBinOpOfIntCasts(BinaryOperator &I);
386 // Should only be called by `foldFBinOpOfIntCasts`.
387 Instruction *foldFBinOpOfIntCastsFromSign(
388 BinaryOperator &BO, bool OpsFromSigned, std::array<Value *, 2> IntOps,
389 Constant *Op1FpC, SmallVectorImpl<WithCache<const Value *>> &OpsKnown);
390 Instruction *foldBinopOfSextBoolToSelect(BinaryOperator &I);
391 Instruction *narrowBinOp(TruncInst &Trunc);
392 Instruction *narrowMaskedBinOp(BinaryOperator &And);
393 Instruction *narrowMathIfNoOverflow(BinaryOperator &I);
394 Instruction *narrowFunnelShift(TruncInst &Trunc);
395 Instruction *optimizeBitCastFromPhi(CastInst &CI, PHINode *PN);
396 Instruction *matchSAddSubSat(IntrinsicInst &MinMax1);
397 Instruction *foldNot(BinaryOperator &I);
398 Instruction *foldBinOpOfDisplacedShifts(BinaryOperator &I);
399
400 /// Determine if a pair of casts can be replaced by a single cast.
401 ///
402 /// \param CI1 The first of a pair of casts.
403 /// \param CI2 The second of a pair of casts.
404 ///
405 /// \return 0 if the cast pair cannot be eliminated, otherwise returns an
406 /// Instruction::CastOps value for a cast that can replace the pair, casting
407 /// CI1->getSrcTy() to CI2->getDstTy().
408 ///
409 /// \see CastInst::isEliminableCastPair
410 Instruction::CastOps isEliminableCastPair(const CastInst *CI1,
411 const CastInst *CI2);
412 Value *simplifyIntToPtrRoundTripCast(Value *Val);
413
414 Value *foldAndOrOfICmps(Value *LHS, Value *RHS, Instruction &I, bool IsAnd,
415 bool IsLogical = false);
416 Value *foldXorOfICmps(ICmpInst *LHS, ICmpInst *RHS, BinaryOperator &Xor);
417
418 Value *foldEqOfParts(Value *Cmp0, Value *Cmp1, bool IsAnd);
419
420 Value *foldAndOrOfICmpsUsingRanges(CmpPredicate PredL, Value *LHS0,
421 Value *LHS1, bool LHSOneUse,
422 CmpPredicate PredR, Value *RHS0,
423 Value *RHS1, bool RHSOneUse, bool IsAnd);
424
425 /// Optimize (fcmp)&(fcmp) or (fcmp)|(fcmp).
426 /// NOTE: Unlike most of instcombine, this returns a Value which should
427 /// already be inserted into the function.
428 Value *foldLogicOfFCmps(FCmpInst *LHS, FCmpInst *RHS, bool IsAnd,
429 bool IsLogicalSelect = false);
430
431 Instruction *foldLogicOfIsFPClass(BinaryOperator &Operator, Value *LHS,
432 Value *RHS);
433
434 Value *foldBooleanAndOr(Value *LHS, Value *RHS, Instruction &I, bool IsAnd,
435 bool IsLogical);
436
437 Value *reassociateBooleanAndOr(Value *LHS, Value *X, Value *Y, Instruction &I,
438 bool IsAnd, bool RHSIsLogical);
439
440 Value *foldDisjointOr(Value *LHS, Value *RHS);
441
442 Value *reassociateDisjointOr(Value *LHS, Value *RHS);
443
444 Instruction *
445 canonicalizeConditionalNegationViaMathToSelect(BinaryOperator &i);
446
447 Value *matchSelectFromAndOr(Value *A, Value *B, Value *C, Value *D,
448 bool InvertFalseVal = false);
449 Value *getSelectCondition(Value *A, Value *B, bool ABIsTheSame);
450
451 bool canEvaluateShifted(Value *V, unsigned NumBits, bool IsLeftShift,
452 ShiftSemantics Semantics, Instruction *CtxI);
453 Value *getShiftedValue(Value *V, unsigned NumBits, bool IsLeftShift,
454 ShiftSemantics Semantics);
455
456 Instruction *foldLShrOverflowBit(BinaryOperator &I);
457 Instruction *foldExtractOfOverflowIntrinsic(ExtractValueInst &EV);
458 Instruction *foldIntrinsicWithOverflowCommon(IntrinsicInst *II);
459 Instruction *foldIntrinsicIsFPClass(IntrinsicInst &II);
460 Instruction *foldFPSignBitOps(BinaryOperator &I);
461 Instruction *foldFDivConstantDivisor(BinaryOperator &I);
462
463 // Optimize one of these forms:
464 // and i1 Op, SI / select i1 Op, i1 SI, i1 false (if IsAnd = true)
465 // or i1 Op, SI / select i1 Op, i1 true, i1 SI (if IsAnd = false)
466 // into simplier select instruction using isImpliedCondition.
467 Instruction *foldAndOrOfSelectUsingImpliedCond(Value *Op, SelectInst &SI,
468 bool IsAnd);
469
470 Instruction *hoistFNegAboveFMulFDiv(Value *FNegOp, Instruction &FMFSource);
471
472 /// Simplify \p V given that it is known to be non-null.
473 /// Returns the simplified value if possible, otherwise returns nullptr.
474 /// If \p UseProvenance is true, the simplification will use provenance-based
475 /// reasoning (if the pointer is known to be dereferenceable in an
476 /// address-space where null is not defined).
477 Value *simplifyNonNullOperand(Value *V, bool UseProvenance,
478 unsigned Depth = 0);
479
480 /// Create `select C, S1, S2`. Use only when the profile cannot be calculated
481 /// from existing profile metadata: if the Function has profiles, this will
482 /// set the profile of this select to "unknown".
483 SelectInst *
484 createSelectInstWithUnknownProfile(Value *C, Value *S1, Value *S2,
485 const Twine &NameStr = "",
486 InsertPosition InsertBefore = nullptr) {
487 auto *Sel = SelectInst::Create(C, S1, S2, NameStr, InsertBefore, MDFrom: nullptr);
488 setExplicitlyUnknownBranchWeightsIfProfiled(I&: *Sel, DEBUG_TYPE, F: &F);
489 return Sel;
490 }
491
492public:
493 /// Create and insert the idiom we use to indicate a block is unreachable
494 /// without having to rewrite the CFG from within InstCombine.
495 void CreateNonTerminatorUnreachable(Instruction *InsertAt) {
496 auto &Ctx = InsertAt->getContext();
497 auto *SI = new StoreInst(ConstantInt::getTrue(Context&: Ctx),
498 PoisonValue::get(T: PointerType::getUnqual(C&: Ctx)),
499 /*isVolatile*/ false, Align(1));
500 InsertNewInstWith(New: SI, Old: InsertAt->getIterator());
501 }
502
503 /// Combiner aware instruction erasure.
504 ///
505 /// When dealing with an instruction that has side effects or produces a void
506 /// value, we can't rely on DCE to delete the instruction. Instead, visit
507 /// methods should return the value returned by this function.
508 Instruction *eraseInstFromFunction(Instruction &I) override {
509 LLVM_DEBUG(dbgs() << "IC: ERASE " << I << '\n');
510 assert(I.use_empty() && "Cannot erase instruction that is used!");
511 salvageDebugInfo(I);
512
513 // Make sure that we reprocess all operands now that we reduced their
514 // use counts.
515 SmallVector<Value *> Ops(I.operands());
516 Worklist.remove(I: &I);
517 DC.removeValue(V: &I);
518 I.eraseFromParent();
519 for (Value *Op : Ops)
520 Worklist.handleUseCountDecrement(V: Op);
521 MadeIRChange = true;
522 return nullptr; // Don't do anything with FI
523 }
524
525 OverflowResult computeOverflow(
526 Instruction::BinaryOps BinaryOp, bool IsSigned,
527 Value *LHS, Value *RHS, Instruction *CtxI) const;
528
529 /// Performs a few simplifications for operators which are associative
530 /// or commutative.
531 bool SimplifyAssociativeOrCommutative(BinaryOperator &I);
532
533 /// If InnerVal1 and OuterVal form a symmetric pair, and "op" is commutative:
534 /// "(InnerVal0 op InnerVal1) op OuterVal" ==> "(X op' Y) op InnerVal0".
535 /// "OuterVal op (InnerVal0 op InnerVal1)" ==> "InnerVal0 op (X op' Y)".
536 /// X and Y are the inputs to the symmetric pair. "op'" indicates that
537 /// InnerOp will have its poison-generating flags dropped.
538 bool tryReassociateAndFoldSymmetricPair(BinaryOperator &OuterOp,
539 BinaryOperator &InnerOp,
540 Value *InnerVal0, Value *InnerVal1,
541 Value *OuterVal);
542
543 /// Tries to simplify binary operations which some other binary
544 /// operation distributes over.
545 ///
546 /// It does this by either by factorizing out common terms (eg "(A*B)+(A*C)"
547 /// -> "A*(B+C)") or expanding out if this results in simplifications (eg: "A
548 /// & (B | C) -> (A&B) | (A&C)" if this is a win). Returns the simplified
549 /// value, or null if it didn't simplify.
550 Value *foldUsingDistributiveLaws(BinaryOperator &I);
551
552 /// Tries to simplify add operations using the definition of remainder.
553 ///
554 /// The definition of remainder is X % C = X - (X / C ) * C. The add
555 /// expression X % C0 + (( X / C0 ) % C1) * C0 can be simplified to
556 /// X % (C0 * C1)
557 Value *SimplifyAddWithRemainder(BinaryOperator &I);
558
559 // Binary Op helper for select operations where the expression can be
560 // efficiently reorganized.
561 Value *SimplifySelectsFeedingBinaryOp(BinaryOperator &I, Value *LHS,
562 Value *RHS);
563
564 /// Given that \p CondVal is known to be \p CondIsTrue, try to simplify
565 /// \p SI to one of its arms.
566 Value *simplifyNestedSelectsUsingImpliedCond(SelectInst &SI, Value *CondVal,
567 bool CondIsTrue);
568
569 // If `I` has operand `(ctpop (not x))`, fold `I` with `(sub nuw nsw
570 // BitWidth(x), (ctpop x))`.
571 Instruction *tryFoldInstWithCtpopWithNot(Instruction *I);
572
573 // (Binop1 (Binop2 (logic_shift X, C), C1), (logic_shift Y, C))
574 // -> (logic_shift (Binop1 (Binop2 X, inv_logic_shift(C1, C)), Y), C)
575 // (Binop1 (Binop2 (logic_shift X, Amt), Mask), (logic_shift Y, Amt))
576 // -> (BinOp (logic_shift (BinOp X, Y)), Mask)
577 Instruction *foldBinOpShiftWithShift(BinaryOperator &I);
578
579 /// Tries to simplify binops of select and cast of the select condition.
580 ///
581 /// (Binop (cast C), (select C, T, F))
582 /// -> (select C, C0, C1)
583 Instruction *foldBinOpOfSelectAndCastOfSelectCondition(BinaryOperator &I);
584 /// Fold both forms of the div_ceil idiom:
585 /// (add (udiv X, Y), (zext (icmp ne (urem X, Y), 0)))
586 /// -> (udiv (add nuw X, Y-1), Y)
587 /// (add (zext (udiv X, Y)), (zext (icmp ne (urem X, Y), 0)))
588 /// -> (zext (udiv (add nuw X, Y-1), Y))
589 Instruction *foldDivCeil(BinaryOperator &I);
590
591 /// This tries to simplify binary operations by factorizing out common terms
592 /// (e. g. "(A*B)+(A*C)" -> "A*(B+C)").
593 Value *tryFactorizationFolds(BinaryOperator &I);
594
595 /// Match a select chain which produces one of three values based on whether
596 /// the LHS is less than, equal to, or greater than RHS respectively.
597 /// Return true if we matched a three way compare idiom. The LHS, RHS, Less,
598 /// Equal and Greater values are saved in the matching process and returned to
599 /// the caller.
600 bool matchThreeWayIntCompare(SelectInst *SI, Value *&LHS, Value *&RHS,
601 ConstantInt *&Less, ConstantInt *&Equal,
602 ConstantInt *&Greater);
603
604 /// Attempts to replace I with a simpler value based on the demanded
605 /// bits.
606 Value *SimplifyDemandedUseBits(Instruction *I, const APInt &DemandedMask,
607 KnownBits &Known, const SimplifyQuery &Q,
608 unsigned Depth = 0);
609 using InstCombiner::SimplifyDemandedBits;
610 bool SimplifyDemandedBits(Instruction *I, unsigned Op,
611 const APInt &DemandedMask, KnownBits &Known,
612 const SimplifyQuery &Q,
613 unsigned Depth = 0) override;
614
615 /// Helper routine of SimplifyDemandedUseBits. It computes KnownZero/KnownOne
616 /// bits. It also tries to handle simplifications that can be done based on
617 /// DemandedMask, but without modifying the Instruction.
618 Value *SimplifyMultipleUseDemandedBits(Instruction *I,
619 const APInt &DemandedMask,
620 KnownBits &Known,
621 const SimplifyQuery &Q,
622 unsigned Depth = 0);
623
624 /// Helper routine of SimplifyDemandedUseBits. It tries to simplify demanded
625 /// bit for "r1 = shr x, c1; r2 = shl r1, c2" instruction sequence.
626 Value *simplifyShrShlDemandedBits(
627 Instruction *Shr, const APInt &ShrOp1, Instruction *Shl,
628 const APInt &ShlOp1, const APInt &DemandedMask, KnownBits &Known);
629
630 /// Tries to simplify operands to an integer instruction based on its
631 /// demanded bits.
632 bool SimplifyDemandedInstructionBits(Instruction &Inst);
633 bool SimplifyDemandedInstructionBits(Instruction &Inst, KnownBits &Known);
634
635 Value *SimplifyDemandedVectorElts(Value *V, APInt DemandedElts,
636 APInt &PoisonElts, unsigned Depth = 0,
637 bool AllowMultipleUsers = false) override;
638
639 /// Attempts to replace V with a simpler value based on the demanded
640 /// floating-point classes
641 Value *SimplifyDemandedUseFPClass(Instruction *I, FPClassTest DemandedMask,
642 KnownFPClass &Known, const SimplifyQuery &Q,
643 unsigned Depth = 0);
644 Value *SimplifyMultipleUseDemandedFPClass(Instruction *I,
645 FPClassTest DemandedMask,
646 KnownFPClass &Known,
647 const SimplifyQuery &Q,
648 unsigned Depth);
649
650 bool SimplifyDemandedFPClass(Instruction *I, unsigned Op,
651 FPClassTest DemandedMask, KnownFPClass &Known,
652 const SimplifyQuery &Q, unsigned Depth = 0);
653
654 bool SimplifyDemandedInstructionFPClass(Instruction &Inst);
655
656 /// Common transforms for add / disjoint or
657 Instruction *foldAddLikeCommutative(Value *LHS, Value *RHS, bool NSW,
658 bool NUW);
659
660 /// Canonicalize the position of binops relative to shufflevector.
661 Instruction *foldVectorBinop(BinaryOperator &Inst);
662 Instruction *foldVectorSelect(SelectInst &Sel);
663 Instruction *foldSelectShuffle(ShuffleVectorInst &Shuf);
664 Constant *unshuffleConstant(ArrayRef<int> ShMask, Constant *C,
665 VectorType *NewCTy);
666
667 /// Given a binary operator, cast instruction, or select which has a PHI node
668 /// as operand #0, see if we can fold the instruction into the PHI (which is
669 /// only possible if all operands to the PHI are constants).
670 Instruction *foldOpIntoPhi(Instruction &I, PHINode *PN,
671 bool AllowMultipleUses = false);
672
673 /// Try to fold binary operators whose operands are simple interleaved
674 /// recurrences to a single recurrence. This is a common pattern in reduction
675 /// operations.
676 /// Example:
677 /// %phi1 = phi [init1, %BB1], [%op1, %BB2]
678 /// %phi2 = phi [init2, %BB1], [%op2, %BB2]
679 /// %op1 = binop %phi1, constant1
680 /// %op2 = binop %phi2, constant2
681 /// %rdx = binop %op1, %op2
682 /// -->
683 /// %phi_combined = phi [init_combined, %BB1], [%op_combined, %BB2]
684 /// %rdx_combined = binop %phi_combined, constant_combined
685 Instruction *foldBinopWithRecurrence(BinaryOperator &BO);
686
687 /// For a binary operator with 2 phi operands, try to hoist the binary
688 /// operation before the phi. This can result in fewer instructions in
689 /// patterns where at least one set of phi operands simplifies.
690 /// Example:
691 /// BB3: binop (phi [X, BB1], [C1, BB2]), (phi [Y, BB1], [C2, BB2])
692 /// -->
693 /// BB1: BO = binop X, Y
694 /// BB3: phi [BO, BB1], [(binop C1, C2), BB2]
695 Instruction *foldBinopWithPhiOperands(BinaryOperator &BO);
696
697 /// Given an instruction with a select as one operand and a constant as the
698 /// other operand, try to fold the binary operator into the select arguments.
699 /// This also works for Cast instructions, which obviously do not have a
700 /// second operand.
701 Instruction *FoldOpIntoSelect(Instruction &Op, SelectInst *SI,
702 bool FoldWithMultiUse = false,
703 bool SimplifyBothArms = false);
704
705 Instruction *foldBinOpSelectBinOp(BinaryOperator &Op);
706
707 /// This is a convenience wrapper function for the above two functions.
708 Instruction *foldBinOpIntoSelectOrPhi(BinaryOperator &I);
709
710 Instruction *foldAddWithConstant(BinaryOperator &Add);
711
712 Instruction *foldSquareSumInt(BinaryOperator &I);
713 Instruction *foldSquareSumFP(BinaryOperator &I);
714
715 /// Try to rotate an operation below a PHI node, using PHI nodes for
716 /// its operands.
717 Instruction *foldPHIArgOpIntoPHI(PHINode &PN);
718 Instruction *foldPHIArgBinOpIntoPHI(PHINode &PN);
719 Instruction *foldPHIArgInsertValueInstructionIntoPHI(PHINode &PN);
720 Instruction *foldPHIArgExtractValueInstructionIntoPHI(PHINode &PN);
721 Instruction *foldPHIArgGEPIntoPHI(PHINode &PN);
722 Instruction *foldPHIArgLoadIntoPHI(PHINode &PN);
723 Instruction *foldPHIArgZextsIntoPHI(PHINode &PN);
724 Instruction *foldPHIArgIntToPtrToPHI(PHINode &PN);
725
726 /// If the phi is within a phi web, which is formed by the def-use chain
727 /// of phis and all the phis in the web are only used in the other phis.
728 /// In this case, these phis are dead and we will remove all of them.
729 bool foldDeadPhiWeb(PHINode &PN);
730
731 /// If an integer typed PHI has only one use which is an IntToPtr operation,
732 /// replace the PHI with an existing pointer typed PHI if it exists. Otherwise
733 /// insert a new pointer typed PHI and replace the original one.
734 bool foldIntegerTypedPHI(PHINode &PN);
735
736 /// Helper function for FoldPHIArgXIntoPHI() to set debug location for the
737 /// folded operation.
738 void PHIArgMergedDebugLoc(Instruction *Inst, PHINode &PN);
739
740 Value *foldPtrToIntOrAddrOfGEP(Type *IntTy, Value *Ptr);
741 Instruction *foldGEPICmp(GEPOperator *GEPLHS, Value *RHS, CmpPredicate Cond,
742 Instruction &I);
743 Instruction *foldSelectICmp(CmpPredicate Pred, SelectInst *SI, Value *RHS,
744 const ICmpInst &I);
745 bool foldAllocaCmp(AllocaInst *Alloca);
746 Instruction *foldCmpLoadFromIndexedGlobal(LoadInst *LI, CmpPredicate Pred,
747 Constant *RHSC, Instruction &CtxI,
748 ConstantInt *AndCst = nullptr);
749 Instruction *foldFCmpIntToFPConst(FCmpInst &I, Instruction *LHSI,
750 Constant *RHSC);
751 Instruction *foldICmpAddOpConst(Value *X, const APInt &C, CmpPredicate Pred);
752 Instruction *foldCmpSelectOfConstants(CmpInst &I);
753 Instruction *foldICmpWithCastOp(ICmpInst &ICmp);
754 Instruction *foldICmpWithZextOrSext(ICmpInst &ICmp);
755
756 Instruction *foldICmpUsingKnownBits(ICmpInst &Cmp);
757 Instruction *foldICmpWithDominatingICmp(ICmpInst &Cmp);
758 Instruction *foldICmpWithConstant(ICmpInst &Cmp);
759 Instruction *foldIsMultipleOfAPowerOfTwo(ICmpInst &Cmp);
760 Instruction *foldICmpUsingBoolRange(ICmpInst &I);
761 Instruction *foldICmpInstWithConstant(ICmpInst &Cmp);
762 Instruction *foldICmpInstWithConstantNotInt(ICmpInst &Cmp);
763 Instruction *foldICmpInstWithConstantAllowPoison(ICmpInst &Cmp,
764 const APInt &C);
765 /// Match Op0 Pred Op1 on binops with a removable common operand.
766 bool matchCommonBinOpOperands(Value *Op0, Value *Op1, CmpInst::Predicate Pred,
767 Value *&LHS, Value *&RHS,
768 const SimplifyQuery &Q);
769 Instruction *foldICmpBinOp(ICmpInst &Cmp, const SimplifyQuery &SQ);
770 Instruction *foldICmpWithMinMax(Instruction &I, MinMaxIntrinsic *MinMax,
771 Value *Z, CmpPredicate Pred);
772 Instruction *foldICmpWithClamp(ICmpInst &Cmp, Value *X, MinMaxIntrinsic *Min);
773 Instruction *foldICmpEquality(ICmpInst &Cmp);
774 Instruction *foldIRemByPowerOfTwoToBitTest(ICmpInst &I);
775 Instruction *foldSignBitTest(ICmpInst &I);
776 Instruction *foldICmpWithZero(ICmpInst &Cmp);
777
778 Value *foldMultiplicationOverflowCheck(ICmpInst &Cmp);
779
780 Instruction *foldICmpBinOpWithConstant(ICmpInst &Cmp, BinaryOperator *BO,
781 const APInt &C);
782 Instruction *foldICmpSelectConstant(ICmpInst &Cmp, SelectInst *Select,
783 ConstantInt *C);
784 Instruction *foldICmpTruncConstant(ICmpInst &Cmp, TruncInst *Trunc,
785 const APInt &C);
786 Instruction *foldICmpTruncWithTruncOrExt(ICmpInst &Cmp,
787 const SimplifyQuery &Q);
788 Instruction *foldICmpAndConstant(ICmpInst &Cmp, BinaryOperator *And,
789 const APInt &C);
790 Instruction *foldICmpXorConstant(ICmpInst &Cmp, BinaryOperator *Xor,
791 const APInt &C);
792 Instruction *foldICmpOrConstant(ICmpInst &Cmp, BinaryOperator *Or,
793 const APInt &C);
794 Instruction *foldICmpMulConstant(ICmpInst &Cmp, BinaryOperator *Mul,
795 const APInt &C);
796 Instruction *foldICmpShlConstant(ICmpInst &Cmp, BinaryOperator *Shl,
797 const APInt &C);
798 Instruction *foldICmpShrConstant(ICmpInst &Cmp, BinaryOperator *Shr,
799 const APInt &C);
800 Instruction *foldICmpSRemConstant(ICmpInst &Cmp, BinaryOperator *UDiv,
801 const APInt &C);
802 Instruction *foldICmpUDivConstant(ICmpInst &Cmp, BinaryOperator *UDiv,
803 const APInt &C);
804 Instruction *foldICmpDivConstant(ICmpInst &Cmp, BinaryOperator *Div,
805 const APInt &C);
806 Instruction *foldICmpSubConstant(ICmpInst &Cmp, BinaryOperator *Sub,
807 const APInt &C);
808 Instruction *foldICmpAddConstant(ICmpInst &Cmp, BinaryOperator *Add,
809 const APInt &C);
810 Instruction *foldICmpAndConstConst(ICmpInst &Cmp, BinaryOperator *And,
811 const APInt &C1);
812 Instruction *foldICmpAndShift(ICmpInst &Cmp, BinaryOperator *And,
813 const APInt &C1, const APInt &C2);
814 Instruction *foldICmpXorShiftConst(ICmpInst &Cmp, BinaryOperator *Xor,
815 const APInt &C);
816 Instruction *foldICmpShrConstConst(ICmpInst &I, Value *ShAmt, const APInt &C1,
817 const APInt &C2);
818 Instruction *foldICmpShlConstConst(ICmpInst &I, Value *ShAmt, const APInt &C1,
819 const APInt &C2);
820
821 Instruction *foldICmpBinOpWithConstantViaTruthTable(ICmpInst &Cmp,
822 BinaryOperator *BO,
823 const APInt &C);
824 Instruction *foldICmpBinOpEqualityWithConstant(ICmpInst &Cmp,
825 BinaryOperator *BO,
826 const APInt &C);
827 Instruction *foldICmpIntrinsicWithConstant(ICmpInst &ICI, IntrinsicInst *II,
828 const APInt &C);
829 Instruction *foldICmpEqIntrinsicWithConstant(ICmpInst &ICI, IntrinsicInst *II,
830 const APInt &C);
831 Instruction *foldICmpBitCast(ICmpInst &Cmp);
832 Instruction *foldICmpWithTrunc(ICmpInst &Cmp);
833 Instruction *foldICmpCommutative(CmpPredicate Pred, Value *Op0, Value *Op1,
834 ICmpInst &CtxI);
835
836 // Helpers of visitSelectInst().
837 Instruction *foldSelectOfBools(SelectInst &SI);
838 Instruction *foldSelectToCmp(SelectInst &SI);
839 Instruction *foldSelectExtConst(SelectInst &Sel);
840 Instruction *foldSelectEqualityTest(SelectInst &SI);
841 Instruction *foldSelectOpOp(SelectInst &SI, Instruction *TI, Instruction *FI);
842 Instruction *foldSelectIntrinsic(SelectInst &SI);
843 Instruction *foldSelectIntoOp(SelectInst &SI, Value *, Value *);
844 Instruction *foldSPFofSPF(Instruction *Inner, SelectPatternFlavor SPF1,
845 Value *A, Value *B, Instruction &Outer,
846 SelectPatternFlavor SPF2, Value *C);
847 Instruction *foldSelectInstWithICmp(SelectInst &SI, ICmpInst *ICI);
848 Value *foldSelectWithConstOpToBinOp(ICmpInst *Cmp, Value *TrueVal,
849 Value *FalseVal);
850 Instruction *foldSelectValueEquivalence(SelectInst &SI, CmpInst &CI);
851
852 Instruction *foldExtractionOfVectorDeinterleave(ZExtInst &RootZExt);
853
854 bool replaceInInstruction(Value *V, Value *Old, Value *New,
855 unsigned Depth = 0);
856
857 Value *insertRangeTest(Value *V, const APInt &Lo, const APInt &Hi,
858 bool isSigned, bool Inside);
859 bool mergeStoreIntoSuccessor(StoreInst &SI);
860
861 /// Given an initial instruction, check to see if it is the root of a
862 /// bswap/bitreverse idiom. If so, return the equivalent bswap/bitreverse
863 /// intrinsic.
864 Instruction *matchBSwapOrBitReverse(Instruction &I, bool MatchBSwaps,
865 bool MatchBitReversals);
866
867 Instruction *SimplifyAnyMemTransfer(AnyMemTransferInst *MI);
868 Instruction *SimplifyAnyMemSet(AnyMemSetInst *MI);
869
870 Value *EvaluateInDifferentType(Value *V, Type *Ty, bool isSigned);
871
872 bool tryToSinkInstruction(Instruction *I, BasicBlock *DestBlock);
873 void tryToSinkInstructionDbgVariableRecords(
874 Instruction *I, BasicBlock::iterator InsertPos, BasicBlock *SrcBlock,
875 BasicBlock *DestBlock, SmallVectorImpl<DbgVariableRecord *> &DPUsers);
876
877 bool removeInstructionsBeforeUnreachable(Instruction &I);
878 void addDeadEdge(BasicBlock *From, BasicBlock *To,
879 SmallVectorImpl<BasicBlock *> &Worklist);
880 void handleUnreachableFrom(Instruction *I,
881 SmallVectorImpl<BasicBlock *> &Worklist);
882 void handlePotentiallyDeadBlocks(SmallVectorImpl<BasicBlock *> &Worklist);
883 void handlePotentiallyDeadSuccessors(BasicBlock *BB, BasicBlock *LiveSucc);
884 void freelyInvertAllUsersOf(Value *V, Value *IgnoredUser = nullptr);
885
886 /// Take the exact integer log2 of the value. If DoFold is true, create the
887 /// actual instructions, otherwise return a non-null dummy value. Return
888 /// nullptr on failure. Note, if DoFold is true the caller must ensure that
889 /// takeLog2 will succeed, otherwise it may create stray instructions.
890 Value *takeLog2(Value *Op, unsigned Depth, bool AssumeNonZero, bool DoFold);
891
892 Value *tryGetLog2(Value *Op, bool AssumeNonZero) {
893 if (takeLog2(Op, /*Depth=*/Depth: 0, AssumeNonZero, /*DoFold=*/DoFold: false))
894 return takeLog2(Op, /*Depth=*/Depth: 0, AssumeNonZero, /*DoFold=*/DoFold: true);
895 return nullptr;
896 }
897};
898
899class Negator final {
900 /// Top-to-bottom, def-to-use negated instruction tree we produced.
901 SmallVector<Instruction *, NegatorMaxNodesSSO> NewInstructions;
902
903 using BuilderTy = IRBuilder<TargetFolder, IRBuilderCallbackInserter>;
904 BuilderTy Builder;
905
906 const DominatorTree &DT;
907
908 const bool IsTrulyNegation;
909
910 const unsigned MaxDepth;
911
912 SmallDenseMap<Value *, Value *> NegationsCache;
913
914 Negator(Module &M, const DominatorTree &DT, bool IsTrulyNegation,
915 unsigned MaxDepth);
916
917#if LLVM_ENABLE_STATS
918 unsigned NumValuesVisitedInThisNegator = 0;
919 ~Negator();
920#endif
921
922 using Result = std::pair<ArrayRef<Instruction *> /*NewInstructions*/,
923 Value * /*NegatedRoot*/>;
924
925 std::array<Value *, 2> getSortedOperandsOfBinOp(Instruction *I);
926
927 [[nodiscard]] Value *visitImpl(Value *V, bool IsNSW, unsigned Depth);
928
929 [[nodiscard]] Value *negate(Value *V, bool IsNSW, unsigned Depth);
930
931 /// Recurse depth-first and attempt to sink the negation.
932 /// FIXME: use worklist?
933 [[nodiscard]] std::optional<Result> run(Value *Root, bool IsNSW);
934
935 Negator(const Negator &) = delete;
936 Negator(Negator &&) = delete;
937 Negator &operator=(const Negator &) = delete;
938 Negator &operator=(Negator &&) = delete;
939
940public:
941 /// Attempt to negate \p Root. Retuns nullptr if negation can't be performed,
942 /// otherwise returns negated value.
943 [[nodiscard]] static Value *Negate(bool LHSIsZero, bool IsNSW, Value *Root,
944 InstCombinerImpl &IC);
945};
946
947struct CommonPointerBase {
948 /// Common base pointer.
949 Value *Ptr = nullptr;
950 /// LHS GEPs until common base.
951 SmallVector<GEPOperator *> LHSGEPs;
952 /// RHS GEPs until common base.
953 SmallVector<GEPOperator *> RHSGEPs;
954 /// LHS GEP NoWrapFlags until common base.
955 GEPNoWrapFlags LHSNW = GEPNoWrapFlags::all();
956 /// RHS GEP NoWrapFlags until common base.
957 GEPNoWrapFlags RHSNW = GEPNoWrapFlags::all();
958
959 static CommonPointerBase compute(Value *LHS, Value *RHS);
960
961 /// Whether expanding the GEP chains is expensive.
962 bool isExpensive() const;
963};
964
965} // end namespace llvm
966
967#undef DEBUG_TYPE
968
969#endif // LLVM_LIB_TRANSFORMS_INSTCOMBINE_INSTCOMBINEINTERNAL_H
970