LLVM 24.0.0git
InstCombineInternal.h
Go to the documentation of this file.
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
20#include "llvm/ADT/Statistic.h"
24#include "llvm/IR/IRBuilder.h"
25#include "llvm/IR/InstVisitor.h"
28#include "llvm/IR/Value.h"
29#include "llvm/Support/Debug.h"
34#include <cassert>
35
36#define DEBUG_TYPE "instcombine"
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
66
68 : public InstCombiner,
69 public InstVisitor<InstCombinerImpl, Instruction *> {
70public:
82
83 ~InstCombinerImpl() override = default;
84
85 const InstCombineCLOptions &CLOpts;
86
87 /// Perform early cleanup and prepare the InstCombine worklist.
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 //
106 Value *LHS, Value *RHS, Type *Ty, bool isNUW);
123 Value *simplifyRangeCheck(CmpPredicate PredL, Value *LHS0, Value *LHS1,
124 CmpPredicate PredR, Value *RHS0, Value *RHS1,
125 Instruction *CtxI, bool Inverted);
134 BinaryOperator *Sh0, const SimplifyQuery &SQ,
135 bool AnalyzeForSignBitExtraction = false);
139 BinaryOperator &OldAShr);
163 template <typename FPToIntTy> Instruction *foldItoFPtoI(FPToIntTy &FI);
170
177 Instruction *visitFree(CallInst &FI, Value *FreedOp);
202
203 /// Specify what to return for unhandled instructions.
205
206 /// True when DB dominates all uses of DI except UI.
207 /// UI must be in the same block as DI.
208 /// The routine checks that the DI parent and DB are different.
209 bool dominatesAllUses(const Instruction *DI, const Instruction *UI,
210 const BasicBlock *DB) const;
211
212 /// Try to replace select with select operand SIOpd in SI-ICmp sequence.
213 bool replacedSelectWithOperand(SelectInst *SI, const ICmpInst *Icmp,
214 const unsigned SIOpd);
215
216 LoadInst *combineLoadToNewType(LoadInst &LI, Type *NewTy,
217 const Twine &Suffix = "");
218
219 /// Check if fmul \p MulVal, +0.0 will yield +0.0 (or signed zero is
220 /// ignorable).
222 const Instruction *CtxI) const;
223
224 std::optional<std::pair<Intrinsic::ID, SmallVector<Value *, 3>>>
226
227private:
228 bool annotateAnyAllocSite(CallBase &Call, const TargetLibraryInfo *TLI);
229 bool isDesirableIntType(unsigned BitWidth) const;
230 bool shouldChangeType(unsigned FromBitWidth, unsigned ToBitWidth) const;
231 bool shouldChangeType(Type *From, Type *To) const;
232 Value *dyn_castNegVal(Value *V) const;
233
234 /// Classify whether a cast is worth optimizing.
235 ///
236 /// This is a helper to decide whether the simplification of
237 /// logic(cast(A), cast(B)) to cast(logic(A, B)) should be performed.
238 ///
239 /// \param CI The cast we are interested in.
240 ///
241 /// \return true if this cast actually results in any code being generated and
242 /// if it cannot already be eliminated by some other transformation.
243 bool shouldOptimizeCast(CastInst *CI);
244
245 /// Try to optimize a sequence of instructions checking if an operation
246 /// on LHS and RHS overflows.
247 ///
248 /// If this overflow check is done via one of the overflow check intrinsics,
249 /// then CtxI has to be the call instruction calling that intrinsic. If this
250 /// overflow check is done by arithmetic followed by a compare, then CtxI has
251 /// to be the arithmetic instruction.
252 ///
253 /// If a simplification is possible, stores the simplified result of the
254 /// operation in OperationResult and result of the overflow check in
255 /// OverflowResult, and return true. If no simplification is possible,
256 /// returns false.
257 bool OptimizeOverflowCheck(Instruction::BinaryOps BinaryOp, bool IsSigned,
258 Value *LHS, Value *RHS,
259 Instruction &CtxI, Value *&OperationResult,
261
262 Instruction *visitCallBase(CallBase &Call);
263 Instruction *tryOptimizeCall(CallInst *CI);
264 bool transformConstExprCastCall(CallBase &Call);
265 Instruction *transformCallThroughTrampoline(CallBase &Call,
266 IntrinsicInst &Tramp);
267
268 /// Try to optimize a call to the result of a ptrauth intrinsic, potentially
269 /// into the ptrauth call bundle:
270 /// - call(ptrauth.resign(p)), ["ptrauth"()] -> call p, ["ptrauth"()]
271 /// - call(ptrauth.sign(p)), ["ptrauth"()] -> call p
272 /// as long as the key/discriminator are the same in sign and auth-bundle,
273 /// and we don't change the key in the bundle (to a potentially-invalid key.)
274 Instruction *foldPtrAuthIntrinsicCallee(CallBase &Call);
275
276 /// Try to optimize a call to a ptrauth constant, into its ptrauth bundle:
277 /// call(ptrauth(f)), ["ptrauth"()] -> call f
278 /// as long as the key/discriminator are the same in constant and bundle.
279 Instruction *foldPtrAuthConstantCallee(CallBase &Call);
280
281 // Return (a, b) if (LHS, RHS) is known to be (a, b) or (b, a).
282 // Otherwise, return std::nullopt
283 // Currently it matches:
284 // - LHS = (select c, a, b), RHS = (select c, b, a)
285 // - LHS = (phi [a, BB0], [b, BB1]), RHS = (phi [b, BB0], [a, BB1])
286 // - LHS = min(a, b), RHS = max(a, b)
287 std::optional<std::pair<Value *, Value *>> matchSymmetricPair(Value *LHS,
288 Value *RHS);
289
290 Value *simplifyMaskedLoad(IntrinsicInst &II);
291 Instruction *simplifyMaskedStore(IntrinsicInst &II);
292 Instruction *simplifyMaskedGather(IntrinsicInst &II);
293 Instruction *simplifyMaskedScatter(IntrinsicInst &II);
294
295 /// Transform (zext icmp) to bitwise / integer operations in order to
296 /// eliminate it.
297 ///
298 /// \param ICI The icmp of the (zext icmp) pair we are interested in.
299 /// \parem CI The zext of the (zext icmp) pair we are interested in.
300 ///
301 /// \return null if the transformation cannot be performed. If the
302 /// transformation can be performed the new instruction that replaces the
303 /// (zext icmp) pair will be returned.
304 Instruction *transformZExtICmp(ICmpInst *Cmp, ZExtInst &Zext);
305
306 Instruction *transformSExtICmp(ICmpInst *Cmp, SExtInst &Sext);
307
308 bool willNotOverflowSignedAdd(const WithCache<const Value *> &LHS,
310 const Instruction &CtxI) const {
311 return computeOverflowForSignedAdd(LHS, RHS, &CtxI) ==
313 }
314
315 bool willNotOverflowUnsignedAdd(const WithCache<const Value *> &LHS,
317 const Instruction &CtxI) const {
318 return computeOverflowForUnsignedAdd(LHS, RHS, &CtxI) ==
320 }
321
322 bool willNotOverflowAdd(const Value *LHS, const Value *RHS,
323 const Instruction &CtxI, bool IsSigned) const {
324 return IsSigned ? willNotOverflowSignedAdd(LHS, RHS, CtxI)
325 : willNotOverflowUnsignedAdd(LHS, RHS, CtxI);
326 }
327
328 bool willNotOverflowSignedSub(const Value *LHS, const Value *RHS,
329 const Instruction &CtxI) const {
330 return computeOverflowForSignedSub(LHS, RHS, &CtxI) ==
331 OverflowResult::NeverOverflows;
332 }
333
334 bool willNotOverflowUnsignedSub(const Value *LHS, const Value *RHS,
335 const Instruction &CtxI) const {
336 return computeOverflowForUnsignedSub(LHS, RHS, &CtxI) ==
337 OverflowResult::NeverOverflows;
338 }
339
340 bool willNotOverflowSub(const Value *LHS, const Value *RHS,
341 const Instruction &CtxI, bool IsSigned) const {
342 return IsSigned ? willNotOverflowSignedSub(LHS, RHS, CtxI)
343 : willNotOverflowUnsignedSub(LHS, RHS, CtxI);
344 }
345
346 bool willNotOverflowSignedMul(const Value *LHS, const Value *RHS,
347 const Instruction &CtxI) const {
348 return computeOverflowForSignedMul(LHS, RHS, &CtxI) ==
349 OverflowResult::NeverOverflows;
350 }
351
352 bool willNotOverflowUnsignedMul(const Value *LHS, const Value *RHS,
353 const Instruction &CtxI,
354 bool IsNSW = false) const {
355 return computeOverflowForUnsignedMul(LHS, RHS, &CtxI, IsNSW) ==
356 OverflowResult::NeverOverflows;
357 }
358
359 bool willNotOverflowMul(const Value *LHS, const Value *RHS,
360 const Instruction &CtxI, bool IsSigned) const {
361 return IsSigned ? willNotOverflowSignedMul(LHS, RHS, CtxI)
362 : willNotOverflowUnsignedMul(LHS, RHS, CtxI);
363 }
364
365 bool willNotOverflow(BinaryOperator::BinaryOps Opcode, const Value *LHS,
366 const Value *RHS, const Instruction &CtxI,
367 bool IsSigned) const {
368 switch (Opcode) {
369 case Instruction::Add: return willNotOverflowAdd(LHS, RHS, CtxI, IsSigned);
370 case Instruction::Sub: return willNotOverflowSub(LHS, RHS, CtxI, IsSigned);
371 case Instruction::Mul: return willNotOverflowMul(LHS, RHS, CtxI, IsSigned);
372 default: llvm_unreachable("Unexpected opcode for overflow query");
373 }
374 }
375
376 Value *EmitGEPOffset(GEPOperator *GEP, bool RewriteGEP = false);
377 /// Emit sum of multiple GEP offsets. The GEPs are processed in reverse
378 /// order.
379 Value *EmitGEPOffsets(ArrayRef<GEPOperator *> GEPs, GEPNoWrapFlags NW,
380 Type *IdxTy, bool RewriteGEPs);
381 Instruction *scalarizePHI(ExtractElementInst &EI, PHINode *PN);
382 Instruction *foldBitcastExtElt(ExtractElementInst &ExtElt);
383 Instruction *foldCastedBitwiseLogic(BinaryOperator &I);
384 Instruction *foldFBinOpOfIntCasts(BinaryOperator &I);
385 // Should only be called by `foldFBinOpOfIntCasts`.
386 Instruction *foldFBinOpOfIntCastsFromSign(
387 BinaryOperator &BO, bool OpsFromSigned, std::array<Value *, 2> IntOps,
388 Constant *Op1FpC, SmallVectorImpl<WithCache<const Value *>> &OpsKnown);
389 Instruction *foldBinopOfSextBoolToSelect(BinaryOperator &I);
390 Instruction *narrowBinOp(TruncInst &Trunc);
391 Instruction *narrowMaskedBinOp(BinaryOperator &And);
392 Instruction *narrowMathIfNoOverflow(BinaryOperator &I);
393 Instruction *narrowFunnelShift(TruncInst &Trunc);
394 Instruction *optimizeBitCastFromPhi(CastInst &CI, PHINode *PN);
395 Instruction *matchSAddSubSat(IntrinsicInst &MinMax1);
396 Instruction *foldNot(BinaryOperator &I);
397 Instruction *foldBinOpOfDisplacedShifts(BinaryOperator &I);
398
399 /// Determine if a pair of casts can be replaced by a single cast.
400 ///
401 /// \param CI1 The first of a pair of casts.
402 /// \param CI2 The second of a pair of casts.
403 ///
404 /// \return 0 if the cast pair cannot be eliminated, otherwise returns an
405 /// Instruction::CastOps value for a cast that can replace the pair, casting
406 /// CI1->getSrcTy() to CI2->getDstTy().
407 ///
408 /// \see CastInst::isEliminableCastPair
409 Instruction::CastOps isEliminableCastPair(const CastInst *CI1,
410 const CastInst *CI2);
411 Value *simplifyIntToPtrRoundTripCast(Value *Val);
412
413 Value *foldAndOrOfICmps(Value *LHS, Value *RHS, Instruction &I, bool IsAnd,
414 bool IsLogical = false);
415 Value *foldXorOfICmps(ICmpInst *LHS, ICmpInst *RHS, BinaryOperator &Xor);
416
417 Value *foldEqOfParts(Value *Cmp0, Value *Cmp1, bool IsAnd);
418
419 Value *foldAndOrOfICmpsUsingRanges(CmpPredicate PredL, Value *LHS0,
420 Value *LHS1, bool LHSOneUse,
421 CmpPredicate PredR, Value *RHS0,
422 Value *RHS1, bool RHSOneUse, bool IsAnd);
423
424 /// Optimize (fcmp)&(fcmp) or (fcmp)|(fcmp).
425 /// NOTE: Unlike most of instcombine, this returns a Value which should
426 /// already be inserted into the function.
427 Value *foldLogicOfFCmps(FCmpInst *LHS, FCmpInst *RHS, bool IsAnd,
428 bool IsLogicalSelect = false);
429
430 Instruction *foldLogicOfIsFPClass(BinaryOperator &Operator, Value *LHS,
431 Value *RHS);
432
433 Value *foldBooleanAndOr(Value *LHS, Value *RHS, Instruction &I, bool IsAnd,
434 bool IsLogical);
435
436 Value *reassociateBooleanAndOr(Value *LHS, Value *X, Value *Y, Instruction &I,
437 bool IsAnd, bool RHSIsLogical);
438
439 Value *foldDisjointOr(Value *LHS, Value *RHS);
440
441 Value *reassociateDisjointOr(Value *LHS, Value *RHS);
442
444 canonicalizeConditionalNegationViaMathToSelect(BinaryOperator &i);
445
446 Value *matchSelectFromAndOr(Value *A, Value *B, Value *C, Value *D,
447 bool InvertFalseVal = false);
448 Value *getSelectCondition(Value *A, Value *B, bool ABIsTheSame);
449
450 bool canEvaluateShifted(Value *V, unsigned NumBits, bool IsLeftShift,
451 ShiftSemantics Semantics, Instruction *CtxI);
452 Value *getShiftedValue(Value *V, unsigned NumBits, bool IsLeftShift,
453 ShiftSemantics Semantics);
454
455 Instruction *foldLShrOverflowBit(BinaryOperator &I);
456 Instruction *foldExtractOfOverflowIntrinsic(ExtractValueInst &EV);
457 Instruction *foldIntrinsicWithOverflowCommon(IntrinsicInst *II);
458 Instruction *foldIntrinsicIsFPClass(IntrinsicInst &II);
459 Instruction *foldFPSignBitOps(BinaryOperator &I);
460 Instruction *foldFDivConstantDivisor(BinaryOperator &I);
461
462 // Optimize one of these forms:
463 // and i1 Op, SI / select i1 Op, i1 SI, i1 false (if IsAnd = true)
464 // or i1 Op, SI / select i1 Op, i1 true, i1 SI (if IsAnd = false)
465 // into simplier select instruction using isImpliedCondition.
466 Instruction *foldAndOrOfSelectUsingImpliedCond(Value *Op, SelectInst &SI,
467 bool IsAnd);
468
469 Instruction *hoistFNegAboveFMulFDiv(Value *FNegOp, Instruction &FMFSource);
470
471 /// Simplify \p V given that it is known to be non-null.
472 /// Returns the simplified value if possible, otherwise returns nullptr.
473 /// If \p UseProvenance is true, the simplification will use provenance-based
474 /// reasoning (if the pointer is known to be dereferenceable in an
475 /// address-space where null is not defined).
476 Value *simplifyNonNullOperand(Value *V, bool UseProvenance,
477 unsigned Depth = 0);
478
479 /// Create `select C, S1, S2`. Use only when the profile cannot be calculated
480 /// from existing profile metadata: if the Function has profiles, this will
481 /// set the profile of this select to "unknown".
482 SelectInst *
483 createSelectInstWithUnknownProfile(Value *C, Value *S1, Value *S2,
484 const Twine &NameStr = "",
485 InsertPosition InsertBefore = nullptr) {
486 auto *Sel = SelectInst::Create(C, S1, S2, NameStr, InsertBefore, nullptr);
488 return Sel;
489 }
490
491public:
492 /// Create and insert the idiom we use to indicate a block is unreachable
493 /// without having to rewrite the CFG from within InstCombine.
495 auto &Ctx = InsertAt->getContext();
496 auto *SI = new StoreInst(ConstantInt::getTrue(Ctx),
498 /*isVolatile*/ false, Align(1));
499 InsertNewInstWith(SI, InsertAt->getIterator());
500 }
501
502 /// Combiner aware instruction erasure.
503 ///
504 /// When dealing with an instruction that has side effects or produces a void
505 /// value, we can't rely on DCE to delete the instruction. Instead, visit
506 /// methods should return the value returned by this function.
508 LLVM_DEBUG(dbgs() << "IC: ERASE " << I << '\n');
509 assert(I.use_empty() && "Cannot erase instruction that is used!");
511
512 // Make sure that we reprocess all operands now that we reduced their
513 // use counts.
514 SmallVector<Value *> Ops(I.operands());
515 Worklist.remove(&I);
516 DC.removeValue(&I);
517 I.eraseFromParent();
518 for (Value *Op : Ops)
519 Worklist.handleUseCountDecrement(Op);
520 MadeIRChange = true;
521 return nullptr; // Don't do anything with FI
522 }
523
524 OverflowResult computeOverflow(
525 Instruction::BinaryOps BinaryOp, bool IsSigned,
526 Value *LHS, Value *RHS, Instruction *CtxI) const;
527
528 /// Performs a few simplifications for operators which are associative
529 /// or commutative.
530 bool SimplifyAssociativeOrCommutative(BinaryOperator &I);
531
532 /// If InnerVal1 and OuterVal form a symmetric pair, and "op" is commutative:
533 /// "(InnerVal0 op InnerVal1) op OuterVal" ==> "(X op' Y) op InnerVal0".
534 /// "OuterVal op (InnerVal0 op InnerVal1)" ==> "InnerVal0 op (X op' Y)".
535 /// X and Y are the inputs to the symmetric pair. "op'" indicates that
536 /// InnerOp will have its poison-generating flags dropped.
537 bool tryReassociateAndFoldSymmetricPair(BinaryOperator &OuterOp,
538 BinaryOperator &InnerOp,
539 Value *InnerVal0, Value *InnerVal1,
540 Value *OuterVal);
541
542 /// Tries to simplify binary operations which some other binary
543 /// operation distributes over.
544 ///
545 /// It does this by either by factorizing out common terms (eg "(A*B)+(A*C)"
546 /// -> "A*(B+C)") or expanding out if this results in simplifications (eg: "A
547 /// & (B | C) -> (A&B) | (A&C)" if this is a win). Returns the simplified
548 /// value, or null if it didn't simplify.
549 Value *foldUsingDistributiveLaws(BinaryOperator &I);
550
551 /// Tries to simplify add operations using the definition of remainder.
552 ///
553 /// The definition of remainder is X % C = X - (X / C ) * C. The add
554 /// expression X % C0 + (( X / C0 ) % C1) * C0 can be simplified to
555 /// X % (C0 * C1)
556 Value *SimplifyAddWithRemainder(BinaryOperator &I);
557
558 // Binary Op helper for select operations where the expression can be
559 // efficiently reorganized.
560 Value *SimplifySelectsFeedingBinaryOp(BinaryOperator &I, Value *LHS,
561 Value *RHS);
562
563 /// Given that \p CondVal is known to be \p CondIsTrue, try to simplify
564 /// \p SI to one of its arms.
566 bool CondIsTrue);
567
568 // If `I` has operand `(ctpop (not x))`, fold `I` with `(sub nuw nsw
569 // BitWidth(x), (ctpop x))`.
571
572 // (Binop1 (Binop2 (logic_shift X, C), C1), (logic_shift Y, C))
573 // -> (logic_shift (Binop1 (Binop2 X, inv_logic_shift(C1, C)), Y), C)
574 // (Binop1 (Binop2 (logic_shift X, Amt), Mask), (logic_shift Y, Amt))
575 // -> (BinOp (logic_shift (BinOp X, Y)), Mask)
577
578 /// Tries to simplify binops of select and cast of the select condition.
579 ///
580 /// (Binop (cast C), (select C, T, F))
581 /// -> (select C, C0, C1)
583 /// Fold both forms of the div_ceil idiom:
584 /// (add (udiv X, Y), (zext (icmp ne (urem X, Y), 0)))
585 /// -> (udiv (add nuw X, Y-1), Y)
586 /// (add (zext (udiv X, Y)), (zext (icmp ne (urem X, Y), 0)))
587 /// -> (zext (udiv (add nuw X, Y-1), Y))
589
590 /// This tries to simplify binary operations by factorizing out common terms
591 /// (e. g. "(A*B)+(A*C)" -> "A*(B+C)").
593
594 /// Match a select chain which produces one of three values based on whether
595 /// the LHS is less than, equal to, or greater than RHS respectively.
596 /// Return true if we matched a three way compare idiom. The LHS, RHS, Less,
597 /// Equal and Greater values are saved in the matching process and returned to
598 /// the caller.
600 ConstantInt *&Less, ConstantInt *&Equal,
601 ConstantInt *&Greater);
602
603 /// Attempts to replace I with a simpler value based on the demanded
604 /// bits.
605 Value *SimplifyDemandedUseBits(Instruction *I, const APInt &DemandedMask,
606 KnownBits &Known, const SimplifyQuery &Q,
607 unsigned Depth = 0);
609 bool SimplifyDemandedBits(Instruction *I, unsigned Op,
610 const APInt &DemandedMask, KnownBits &Known,
611 const SimplifyQuery &Q,
612 unsigned Depth = 0) override;
613
614 /// Helper routine of SimplifyDemandedUseBits. It computes KnownZero/KnownOne
615 /// bits. It also tries to handle simplifications that can be done based on
616 /// DemandedMask, but without modifying the Instruction.
618 const APInt &DemandedMask,
620 const SimplifyQuery &Q,
621 unsigned Depth = 0);
622
623 /// Helper routine of SimplifyDemandedUseBits. It tries to simplify demanded
624 /// bit for "r1 = shr x, c1; r2 = shl r1, c2" instruction sequence.
626 Instruction *Shr, const APInt &ShrOp1, Instruction *Shl,
627 const APInt &ShlOp1, const APInt &DemandedMask, KnownBits &Known);
628
629 /// Tries to simplify operands to an integer instruction based on its
630 /// demanded bits.
633
635 APInt &PoisonElts, unsigned Depth = 0,
636 bool AllowMultipleUsers = false) override;
637
638 /// Attempts to replace V with a simpler value based on the demanded
639 /// floating-point classes
642 unsigned Depth = 0);
644 FPClassTest DemandedMask,
646 const SimplifyQuery &Q,
647 unsigned Depth);
648
649 bool SimplifyDemandedFPClass(Instruction *I, unsigned Op,
650 FPClassTest DemandedMask, KnownFPClass &Known,
651 const SimplifyQuery &Q, unsigned Depth = 0);
652
654
655 /// Common transforms for add / disjoint or
657 bool NUW);
658
659 /// Canonicalize the position of binops relative to shufflevector.
664 VectorType *NewCTy);
665
666 /// Given a binary operator, cast instruction, or select which has a PHI node
667 /// as operand #0, see if we can fold the instruction into the PHI (which is
668 /// only possible if all operands to the PHI are constants).
670 bool AllowMultipleUses = false);
671
672 /// Try to fold binary operators whose operands are simple interleaved
673 /// recurrences to a single recurrence. This is a common pattern in reduction
674 /// operations.
675 /// Example:
676 /// %phi1 = phi [init1, %BB1], [%op1, %BB2]
677 /// %phi2 = phi [init2, %BB1], [%op2, %BB2]
678 /// %op1 = binop %phi1, constant1
679 /// %op2 = binop %phi2, constant2
680 /// %rdx = binop %op1, %op2
681 /// -->
682 /// %phi_combined = phi [init_combined, %BB1], [%op_combined, %BB2]
683 /// %rdx_combined = binop %phi_combined, constant_combined
685
686 /// For a binary operator with 2 phi operands, try to hoist the binary
687 /// operation before the phi. This can result in fewer instructions in
688 /// patterns where at least one set of phi operands simplifies.
689 /// Example:
690 /// BB3: binop (phi [X, BB1], [C1, BB2]), (phi [Y, BB1], [C2, BB2])
691 /// -->
692 /// BB1: BO = binop X, Y
693 /// BB3: phi [BO, BB1], [(binop C1, C2), BB2]
695
696 /// Given an instruction with a select as one operand and a constant as the
697 /// other operand, try to fold the binary operator into the select arguments.
698 /// This also works for Cast instructions, which obviously do not have a
699 /// second operand.
701 bool FoldWithMultiUse = false,
702 bool SimplifyBothArms = false);
703
705
706 /// This is a convenience wrapper function for the above two functions.
708
710
713
714 /// Try to rotate an operation below a PHI node, using PHI nodes for
715 /// its operands.
724
725 /// If the phi is within a phi web, which is formed by the def-use chain
726 /// of phis and all the phis in the web are only used in the other phis.
727 /// In this case, these phis are dead and we will remove all of them.
728 bool foldDeadPhiWeb(PHINode &PN);
729
730 /// If an integer typed PHI has only one use which is an IntToPtr operation,
731 /// replace the PHI with an existing pointer typed PHI if it exists. Otherwise
732 /// insert a new pointer typed PHI and replace the original one.
734
735 /// Helper function for FoldPHIArgXIntoPHI() to set debug location for the
736 /// folded operation.
738
741 Instruction &I);
743 const ICmpInst &I);
744 bool foldAllocaCmp(AllocaInst *Alloca);
746 Constant *RHSC, Instruction &CtxI,
747 ConstantInt *AndCst = nullptr);
749 Constant *RHSC);
754
763 const APInt &C);
764 /// Match Op0 Pred Op1 on binops with a removable common operand.
766 Value *&LHS, Value *&RHS,
767 const SimplifyQuery &Q);
776
778
780 const APInt &C);
782 ConstantInt *C);
784 const APInt &C);
786 const SimplifyQuery &Q);
788 const APInt &C);
790 const APInt &C);
792 const APInt &C);
794 const APInt &C);
796 const APInt &C);
798 const APInt &C);
800 const APInt &C);
802 const APInt &C);
804 const APInt &C);
806 const APInt &C);
808 const APInt &C);
810 const APInt &C1);
812 const APInt &C1, const APInt &C2);
814 const APInt &C);
816 const APInt &C2);
818 const APInt &C2);
819
821 BinaryOperator *BO,
822 const APInt &C);
824 BinaryOperator *BO,
825 const APInt &C);
827 const APInt &C);
829 const APInt &C);
833 ICmpInst &CtxI);
834
835 // Helpers of visitSelectInst().
844 Value *A, Value *B, Instruction &Outer,
848 Value *FalseVal);
850
852
854 unsigned Depth = 0);
855
856 Value *insertRangeTest(Value *V, const APInt &Lo, const APInt &Hi,
857 bool isSigned, bool Inside);
859
860 /// Given an initial instruction, check to see if it is the root of a
861 /// bswap/bitreverse idiom. If so, return the equivalent bswap/bitreverse
862 /// intrinsic.
864 bool MatchBitReversals);
865
868
870
871 bool tryToSinkInstruction(Instruction *I, BasicBlock *DestBlock);
873 Instruction *I, BasicBlock::iterator InsertPos, BasicBlock *SrcBlock,
875
877 void addDeadEdge(BasicBlock *From, BasicBlock *To,
883 void freelyInvertAllUsersOf(Value *V, Value *IgnoredUser = nullptr);
884
885 /// Take the exact integer log2 of the value. If DoFold is true, create the
886 /// actual instructions, otherwise return a non-null dummy value. Return
887 /// nullptr on failure. Note, if DoFold is true the caller must ensure that
888 /// takeLog2 will succeed, otherwise it may create stray instructions.
889 Value *takeLog2(Value *Op, unsigned Depth, bool AssumeNonZero, bool DoFold);
890
891 Value *tryGetLog2(Value *Op, bool AssumeNonZero) {
892 if (takeLog2(Op, /*Depth=*/0, AssumeNonZero, /*DoFold=*/false))
893 return takeLog2(Op, /*Depth=*/0, AssumeNonZero, /*DoFold=*/true);
894 return nullptr;
895 }
896};
897
898class Negator final {
899 /// Top-to-bottom, def-to-use negated instruction tree we produced.
901
903 BuilderTy Builder;
904
905 const DominatorTree &DT;
906
907 const bool IsTrulyNegation;
908
909 const unsigned MaxDepth;
910
911 SmallDenseMap<Value *, Value *> NegationsCache;
912
913 Negator(Module &M, const DominatorTree &DT, bool IsTrulyNegation,
914 unsigned MaxDepth);
915
916#if LLVM_ENABLE_STATS
917 unsigned NumValuesVisitedInThisNegator = 0;
918 ~Negator();
919#endif
920
921 using Result = std::pair<ArrayRef<Instruction *> /*NewInstructions*/,
922 Value * /*NegatedRoot*/>;
923
924 std::array<Value *, 2> getSortedOperandsOfBinOp(Instruction *I);
925
926 [[nodiscard]] Value *visitImpl(Value *V, bool IsNSW, unsigned Depth);
927
928 [[nodiscard]] Value *negate(Value *V, bool IsNSW, unsigned Depth);
929
930 /// Recurse depth-first and attempt to sink the negation.
931 /// FIXME: use worklist?
932 [[nodiscard]] std::optional<Result> run(Value *Root, bool IsNSW);
933
934 Negator(const Negator &) = delete;
935 Negator(Negator &&) = delete;
936 Negator &operator=(const Negator &) = delete;
937 Negator &operator=(Negator &&) = delete;
938
939public:
940 /// Attempt to negate \p Root. Retuns nullptr if negation can't be performed,
941 /// otherwise returns negated value.
942 [[nodiscard]] static Value *Negate(bool LHSIsZero, bool IsNSW, Value *Root,
943 InstCombinerImpl &IC);
944};
945
947 /// Common base pointer.
948 Value *Ptr = nullptr;
949 /// LHS GEPs until common base.
951 /// RHS GEPs until common base.
953 /// LHS GEP NoWrapFlags until common base.
955 /// RHS GEP NoWrapFlags until common base.
957
959
960 /// Whether expanding the GEP chains is expensive.
961 bool isExpensive() const;
962};
963
964} // end namespace llvm
965
966#undef DEBUG_TYPE
967
968#endif // LLVM_LIB_TRANSFORMS_INSTCOMBINE_INSTCOMBINEINTERNAL_H
SDValue Pred
assert(UImm &&(UImm !=~static_cast< T >(0)) &&"Invalid immediate!")
constexpr LLT S1
AMDGPU Register Bank Select
#define X(NUM, ENUM, NAME)
Definition ELF.h:665
static GCRegistry::Add< ShadowStackGC > C("shadow-stack", "Very portable GC for uncooperative code generators")
static GCRegistry::Add< ErlangGC > A("erlang", "erlang-compatible garbage collector")
static GCRegistry::Add< StatepointGC > D("statepoint-example", "an example strategy for statepoint")
static GCRegistry::Add< OcamlGC > B("ocaml", "ocaml 3.10-compatible GC")
static bool foldICmpWithDominatingICmp(CmpInst *Cmp, const TargetLowering &TLI, bool EnableICmpEqToICmpSt)
For pattern like:
#define LLVM_LIBRARY_VISIBILITY
Definition Compiler.h:137
static bool isSigned(unsigned Opcode)
#define DEBUG_TYPE
Hexagon Common GEP
IRTranslator LLVM IR MI
static constexpr unsigned NegatorMaxNodesSSO
This file provides the interface for the instcombine pass implementation.
const AbstractManglingParser< Derived, Alloc >::OperatorInfo AbstractManglingParser< Derived, Alloc >::Ops[]
#define F(x, y, z)
Definition MD5.cpp:54
#define I(x, y, z)
Definition MD5.cpp:57
uint64_t IntrinsicInst * II
StandardInstrumentations SI(Mod->getContext(), Debug, VerifyEach)
This file builds on the ADT/GraphTraits.h file to build a generic graph post order iterator.
This file contains the declarations for profiling metadata utility functions.
SmallVector< MachineOperand, 4 > Cond
int64_t C1
This file defines the 'Statistic' class, which is designed to be an easy way to expose various metric...
#define LLVM_DEBUG(...)
Definition Debug.h:119
static TableGen::Emitter::Opt Y("gen-skeleton-entry", EmitSkeleton, "Generate example skeleton entry")
static OverflowResult computeOverflowForSignedAdd(const WithCache< const Value * > &LHS, const WithCache< const Value * > &RHS, const AddOperator *Add, const SimplifyQuery &SQ)
Value * RHS
Value * LHS
static const uint32_t IV[8]
Definition blake3_impl.h:83
Class for arbitrary precision integers.
Definition APInt.h:78
This class represents a conversion between pointers from one address space to another.
an instruction to allocate memory on the stack
This class represents any memset intrinsic.
Represent a constant reference to an array (0 or more elements consecutively in memory),...
Definition ArrayRef.h:40
A cache of @llvm.assume calls within a function.
an instruction that atomically reads a memory location, combines it with another value,...
LLVM Basic Block Representation.
Definition BasicBlock.h:62
InstListType::iterator iterator
Instruction iterators...
Definition BasicBlock.h:170
This class represents a no-op cast from one type to another.
BlockFrequencyInfo pass uses BlockFrequencyInfoImpl implementation to estimate IR basic block frequen...
Analysis providing branch probability information.
Base class for all callable instructions (InvokeInst and CallInst) Holds everything related to callin...
CallBr instruction, tracking function calls that may not return control but instead transfer it to a ...
This class represents a function call, abstracting a target machine's calling convention.
This is the base class for all instructions that perform data casts.
Definition InstrTypes.h:512
This class is the base class for the comparison instructions.
Definition InstrTypes.h:728
Predicate
This enumeration lists the possible predicates for CmpInst subclasses.
Definition InstrTypes.h:740
An abstraction over a floating-point predicate, and a pack of an integer predicate with samesign info...
Conditional Branch instruction.
This is the shared class of boolean and integer constants.
Definition Constants.h:87
static LLVM_ABI ConstantInt * getTrue(LLVMContext &Context)
This is an important base class in LLVM.
Definition Constant.h:44
A parsed version of the target data layout string in and methods for querying it.
Definition DataLayout.h:64
Concrete subclass of DominatorTreeBase that is used to compute a normal dominator tree.
Definition Dominators.h:122
This instruction extracts a single (scalar) element from a VectorType value.
This instruction extracts a struct member or array element value from an aggregate value.
This instruction compares its operands according to the predicate given to the constructor.
This class represents a cast from floating point to signed integer.
This class represents a cast from floating point to unsigned integer.
This class represents a truncation of floating point types.
Convenience struct for specifying and reasoning about fast-math flags.
Definition FMF.h:23
An instruction for ordering other memory operations.
This class represents a freeze function that returns random concrete value if an operand is either a ...
Represents flags for the getelementptr instruction/expression.
static GEPNoWrapFlags all()
an instruction for type-safe pointer arithmetic to access elements of arrays and structs
This instruction compares its operands according to the predicate given to the constructor.
This provides a uniform API for creating instructions and inserting them into a basic block: either a...
Definition IRBuilder.h:2990
This instruction inserts a single (scalar) element into a VectorType value.
This instruction inserts a struct field of array element value into an aggregate value.
Instruction * visitMul(BinaryOperator &I)
Instruction * foldICmpShrConstant(ICmpInst &Cmp, BinaryOperator *Shr, const APInt &C)
Fold icmp ({al}shr X, Y), C.
Instruction * foldICmpWithZextOrSext(ICmpInst &ICmp)
Instruction * visitBitExtractInst(BitExtractInst &BE)
Instruction * foldICmpSelectConstant(ICmpInst &Cmp, SelectInst *Select, ConstantInt *C)
Instruction * foldICmpSRemConstant(ICmpInst &Cmp, BinaryOperator *UDiv, const APInt &C)
Instruction * foldBinOpOfSelectAndCastOfSelectCondition(BinaryOperator &I)
Tries to simplify binops of select and cast of the select condition.
Instruction * foldSelectToCmp(SelectInst &SI)
Instruction * visitAdd(BinaryOperator &I)
Instruction * visitCondBrInst(CondBrInst &BI)
bool fmulByZeroIsZero(Value *MulVal, FastMathFlags FMF, const Instruction *CtxI) const
Check if fmul MulVal, +0.0 will yield +0.0 (or signed zero is ignorable).
Instruction * foldICmpBinOpWithConstant(ICmpInst &Cmp, BinaryOperator *BO, const APInt &C)
Fold an icmp with BinaryOp and constant operand: icmp Pred BO, C.
Instruction * foldICmpOrConstant(ICmpInst &Cmp, BinaryOperator *Or, const APInt &C)
Fold icmp (or X, Y), C.
Instruction * canonicalizeCondSignextOfHighBitExtractToSignextHighBitExtract(BinaryOperator &I)
Instruction * foldICmpTruncWithTruncOrExt(ICmpInst &Cmp, const SimplifyQuery &Q)
Fold icmp (trunc nuw/nsw X), (trunc nuw/nsw Y).
Instruction * visitLShr(BinaryOperator &I)
Instruction * foldBinOpIntoSelectOrPhi(BinaryOperator &I)
This is a convenience wrapper function for the above two functions.
Instruction * visitUDiv(BinaryOperator &I)
Instruction * visitOr(BinaryOperator &I)
Instruction * foldSignBitTest(ICmpInst &I)
Fold equality-comparison between zero and any (maybe truncated) right-shift by one-less-than-bitwidth...
Instruction * foldSelectEqualityTest(SelectInst &SI)
Instruction * visitZExt(ZExtInst &Zext)
Instruction * visitGEPOfGEP(GetElementPtrInst &GEP, GEPOperator *Src)
Instruction * foldSelectValueEquivalence(SelectInst &SI, CmpInst &CI)
Instruction * foldCmpLoadFromIndexedGlobal(LoadInst *LI, CmpPredicate Pred, Constant *RHSC, Instruction &CtxI, ConstantInt *AndCst=nullptr)
Try to fold cmp pred (load (gep GV, ...)), cmpcst where GV is a global variable with a constant initi...
Instruction * visitAddrSpaceCast(AddrSpaceCastInst &CI)
Instruction * foldExtractionOfVectorDeinterleave(ZExtInst &RootZExt)
Instruction * foldPHIArgInsertValueInstructionIntoPHI(PHINode &PN)
If we have something like phi [insertvalue(a,b,0), insertvalue(c,d,0)], turn this into a phi[a,...
Instruction * foldBinOpShiftWithShift(BinaryOperator &I)
~InstCombinerImpl() override=default
Instruction * visitSExt(SExtInst &Sext)
Instruction * visitUnreachableInst(UnreachableInst &I)
Instruction * visitURem(BinaryOperator &I)
bool SimplifyDemandedInstructionFPClass(Instruction &Inst)
Instruction * foldSquareSumInt(BinaryOperator &I)
Instruction * foldOpIntoPhi(Instruction &I, PHINode *PN, bool AllowMultipleUses=false)
Given a binary operator, cast instruction, or select which has a PHI node as operand #0,...
Value * insertRangeTest(Value *V, const APInt &Lo, const APInt &Hi, bool isSigned, bool Inside)
Emit a computation of: (V >= Lo && V < Hi) if Inside is true, otherwise (V < Lo || V >= Hi).
void handleUnreachableFrom(Instruction *I, SmallVectorImpl< BasicBlock * > &Worklist)
Instruction * foldICmpBinOp(ICmpInst &Cmp, const SimplifyQuery &SQ)
Try to fold icmp (binop), X or icmp X, (binop).
Instruction * foldVectorSelect(SelectInst &Sel)
Value * SimplifyDemandedVectorElts(Value *V, APInt DemandedElts, APInt &PoisonElts, unsigned Depth=0, bool AllowMultipleUsers=false) override
The specified value produces a vector with any number of elements.
Instruction * visitFreeze(FreezeInst &I)
Instruction * foldICmpSubConstant(ICmpInst &Cmp, BinaryOperator *Sub, const APInt &C)
Fold icmp (sub X, Y), C.
Instruction * foldSelectShuffle(ShuffleVectorInst &Shuf)
Try to fold shuffles that are the equivalent of a vector select.
Instruction * visitLoadInst(LoadInst &LI)
Value * SimplifyDemandedUseFPClass(Instruction *I, FPClassTest DemandedMask, KnownFPClass &Known, const SimplifyQuery &Q, unsigned Depth=0)
Attempts to replace V with a simpler value based on the demanded floating-point classes.
Value * takeLog2(Value *Op, unsigned Depth, bool AssumeNonZero, bool DoFold)
Take the exact integer log2 of the value.
Instruction * visitFPToSI(FPToSIInst &FI)
Instruction * foldICmpWithClamp(ICmpInst &Cmp, Value *X, MinMaxIntrinsic *Min)
Match and fold patterns like: icmp eq/ne X, min(max(X, Lo), Hi) which represents a range check and ca...
Instruction * foldICmpInstWithConstantNotInt(ICmpInst &Cmp)
Handle icmp with constant (but not simple integer constant) RHS.
Instruction * visitAtomicRMWInst(AtomicRMWInst &SI)
Instruction * visitSRem(BinaryOperator &I)
Instruction * foldSPFofSPF(Instruction *Inner, SelectPatternFlavor SPF1, Value *A, Value *B, Instruction &Outer, SelectPatternFlavor SPF2, Value *C)
Instruction * visitTrunc(TruncInst &CI)
bool matchCommonBinOpOperands(Value *Op0, Value *Op1, CmpInst::Predicate Pred, Value *&LHS, Value *&RHS, const SimplifyQuery &Q)
Match Op0 Pred Op1 on binops with a removable common operand.
Instruction * foldBinOpSelectBinOp(BinaryOperator &Op)
In some cases it is beneficial to fold a select into a binary operator.
bool SimplifyDemandedBits(Instruction *I, unsigned Op, const APInt &DemandedMask, KnownBits &Known, const SimplifyQuery &Q, unsigned Depth=0) override
This form of SimplifyDemandedBits simplifies the specified instruction operand if possible,...
Instruction * foldICmpShlConstConst(ICmpInst &I, Value *ShAmt, const APInt &C1, const APInt &C2)
Handle "(icmp eq/ne (shl AP2, A), AP1)" -> (icmp eq/ne A, TrailingZeros(AP1) - TrailingZeros(AP2)).
Instruction * foldSquareSumFP(BinaryOperator &I)
Value * reassociateShiftAmtsOfTwoSameDirectionShifts(BinaryOperator *Sh0, const SimplifyQuery &SQ, bool AnalyzeForSignBitExtraction=false)
Instruction * foldSelectOpOp(SelectInst &SI, Instruction *TI, Instruction *FI)
We have (select c, TI, FI), and we know that TI and FI have the same opcode.
Instruction * visitUIToFP(CastInst &CI)
Instruction * foldPHIArgBinOpIntoPHI(PHINode &PN)
If we have something like phi [add (a,b), add(a,c)] and if a/b/c and the adds all have a single user,...
void handlePotentiallyDeadBlocks(SmallVectorImpl< BasicBlock * > &Worklist)
bool sinkNotIntoLogicalOp(Instruction &I)
Instruction * foldICmpEqIntrinsicWithConstant(ICmpInst &ICI, IntrinsicInst *II, const APInt &C)
Fold an equality icmp with LLVM intrinsic and constant operand.
Instruction * visitPtrToInt(PtrToIntInst &CI)
bool prepareWorklist(Function &F)
Perform early cleanup and prepare the InstCombine worklist.
Instruction * foldSelectIntrinsic(SelectInst &SI)
This transforms patterns of the form: select cond, intrinsic(x, ...), intrinsic(y,...
std::optional< std::pair< Intrinsic::ID, SmallVector< Value *, 3 > > > convertOrOfShiftsToFunnelShift(Instruction &Or)
Instruction * visitFDiv(BinaryOperator &I)
Instruction * FoldOpIntoSelect(Instruction &Op, SelectInst *SI, bool FoldWithMultiUse=false, bool SimplifyBothArms=false)
Given an instruction with a select as one operand and a constant as the other operand,...
Instruction * SimplifyAnyMemSet(AnyMemSetInst *MI)
bool simplifyDivRemOfSelectWithZeroOp(BinaryOperator &I)
Fold a divide or remainder with a select instruction divisor when one of the select operands is zero.
Value * SimplifyMultipleUseDemandedFPClass(Instruction *I, FPClassTest DemandedMask, KnownFPClass &Known, const SimplifyQuery &Q, unsigned Depth)
Helper routine of SimplifyDemandedUseFPClass.
Instruction * foldItoFPtoI(FPToIntTy &FI)
fpto{s/u}i.sat --> X or zext(X) or sext(X) or trunc(X) This is safe if the intermediate type has enou...
Instruction * visitSIToFP(CastInst &CI)
Instruction * visitSub(BinaryOperator &I)
Instruction * visitAShr(BinaryOperator &I)
bool replaceInInstruction(Value *V, Value *Old, Value *New, unsigned Depth=0)
Instruction * visitFree(CallInst &FI, Value *FreedOp)
Instruction * visitInsertValueInst(InsertValueInst &IV)
Try to find redundant insertvalue instructions, like the following ones: %0 = insertvalue { i8,...
Instruction * visitAnd(BinaryOperator &I)
Value * foldMultiplicationOverflowCheck(ICmpInst &Cmp)
Fold (-1 u/ x) u< y ((x * y) ?
Instruction * visitCallBrInst(CallBrInst &CBI)
Instruction * visitExtractValueInst(ExtractValueInst &EV)
Instruction * visitInsertElementInst(InsertElementInst &IE)
void handlePotentiallyDeadSuccessors(BasicBlock *BB, BasicBlock *LiveSucc)
Instruction * foldDivCeil(BinaryOperator &I)
Fold both forms of the div_ceil idiom: (add (udiv X, Y), (zext (icmp ne (urem X, Y),...
Instruction * commonCastTransforms(CastInst &CI)
Implement the transforms common to all CastInst visitors.
Instruction * foldICmpWithConstant(ICmpInst &Cmp)
Fold icmp Pred X, C.
CmpInst * canonicalizeICmpPredicate(CmpInst &I)
If we have a comparison with a non-canonical predicate, if we can update all the users,...
Instruction * foldBinopWithRecurrence(BinaryOperator &BO)
Try to fold binary operators whose operands are simple interleaved recurrences to a single recurrence...
Instruction * eraseInstFromFunction(Instruction &I) override
Combiner aware instruction erasure.
Instruction * foldICmpWithZero(ICmpInst &Cmp)
Instruction * visitExtractElementInst(ExtractElementInst &EI)
Instruction * commonIDivRemTransforms(BinaryOperator &I)
Common integer divide/remainder transforms.
Value * foldReversedIntrinsicOperands(IntrinsicInst *II)
If all arguments of the intrinsic are reverses, try to pull the reverse after the intrinsic.
Instruction * visitPHINode(PHINode &PN)
Instruction * foldICmpBinOpEqualityWithConstant(ICmpInst &Cmp, BinaryOperator *BO, const APInt &C)
Fold an icmp equality instruction with binary operator LHS and constant RHS: icmp eq/ne BO,...
Instruction * foldPHIArgOpIntoPHI(PHINode &PN)
Try to rotate an operation below a PHI node, using PHI nodes for its operands.
Instruction * visitLandingPadInst(LandingPadInst &LI)
Instruction * foldICmpUsingBoolRange(ICmpInst &I)
If one operand of an icmp is effectively a bool (value range of {0,1}), then try to reduce patterns b...
Instruction * foldICmpWithTrunc(ICmpInst &Cmp)
Instruction * foldCmpSelectOfConstants(CmpInst &I)
Fold fcmp/icmp pred (select C1, TV1, FV1), (select C2, TV2, FV2) where all true/false values are cons...
Instruction * foldICmpIntrinsicWithConstant(ICmpInst &ICI, IntrinsicInst *II, const APInt &C)
Fold an icmp with LLVM intrinsic and constant operand: icmp Pred II, C.
Instruction * visitFPTrunc(FPTruncInst &CI)
Instruction * visitStoreInst(StoreInst &SI)
bool matchThreeWayIntCompare(SelectInst *SI, Value *&LHS, Value *&RHS, ConstantInt *&Less, ConstantInt *&Equal, ConstantInt *&Greater)
Match a select chain which produces one of three values based on whether the LHS is less than,...
const InstCombineCLOptions & CLOpts
Value * tryGetLog2(Value *Op, bool AssumeNonZero)
Instruction * foldPHIArgZextsIntoPHI(PHINode &PN)
TODO: This function could handle other cast types, but then it might require special-casing a cast fr...
Instruction * foldSelectInstWithICmp(SelectInst &SI, ICmpInst *ICI)
Instruction * visitFenceInst(FenceInst &FI)
Value * foldPtrToIntOrAddrOfGEP(Type *IntTy, Value *Ptr)
Instruction * visitFCmpInst(FCmpInst &I)
Value * OptimizePointerDifference(Value *LHS, Value *RHS, Type *Ty, bool isNUW)
Optimize pointer differences into the same array into a size.
Value * simplifyNestedSelectsUsingImpliedCond(SelectInst &SI, Value *CondVal, bool CondIsTrue)
Given that CondVal is known to be CondIsTrue, try to simplify SI to one of its arms.
Instruction * visitBitCast(BitCastInst &CI)
Instruction * visitReturnInst(ReturnInst &RI)
bool sinkNotIntoOtherHandOfLogicalOp(Instruction &I)
Instruction * commonIDivTransforms(BinaryOperator &I)
This function implements the transforms common to both integer division instructions (udiv and sdiv).
Instruction * foldICmpUsingKnownBits(ICmpInst &Cmp)
Try to fold the comparison based on range information we can get by checking whether bits are known t...
Instruction * foldICmpDivConstant(ICmpInst &Cmp, BinaryOperator *Div, const APInt &C)
Fold icmp ({su}div X, Y), C.
Instruction * foldIRemByPowerOfTwoToBitTest(ICmpInst &I)
If we have: icmp eq/ne (urem/srem x, y), 0 iff y is a power-of-two, we can replace this with a bit te...
Instruction * foldFCmpIntToFPConst(FCmpInst &I, Instruction *LHSI, Constant *RHSC)
Fold fcmp ([us]itofp x, cst) if possible.
Instruction * visitShl(BinaryOperator &I)
Instruction * visitSwitchInst(SwitchInst &SI)
Instruction * foldICmpUDivConstant(ICmpInst &Cmp, BinaryOperator *UDiv, const APInt &C)
Fold icmp (udiv X, Y), C.
Instruction * visitBitInsertInst(BitInsertInst &BI)
Instruction * visitFAdd(BinaryOperator &I)
Instruction * foldBinopWithPhiOperands(BinaryOperator &BO)
For a binary operator with 2 phi operands, try to hoist the binary operation before the phi.
Value * simplifyShrShlDemandedBits(Instruction *Shr, const APInt &ShrOp1, Instruction *Shl, const APInt &ShlOp1, const APInt &DemandedMask, KnownBits &Known)
Helper routine of SimplifyDemandedUseBits.
Instruction * visitIntToPtr(IntToPtrInst &CI)
Instruction * foldICmpAddOpConst(Value *X, const APInt &C, CmpPredicate Pred)
Fold "icmp pred (X+C), X".
bool SimplifyDemandedFPClass(Instruction *I, unsigned Op, FPClassTest DemandedMask, KnownFPClass &Known, const SimplifyQuery &Q, unsigned Depth=0)
Instruction * foldICmpWithCastOp(ICmpInst &ICmp)
Handle icmp (cast x), (cast or constant).
Instruction * visitFPToUI(FPToUIInst &FI)
Instruction * foldICmpTruncConstant(ICmpInst &Cmp, TruncInst *Trunc, const APInt &C)
Fold icmp (trunc X), C.
bool mergeStoreIntoSuccessor(StoreInst &SI)
Try to transform: if () { *P = v1; } else { *P = v2 } or: *P = v1; if () { *P = v2; }...
Instruction * foldAddLikeCommutative(Value *LHS, Value *RHS, bool NSW, bool NUW)
Common transforms for add / disjoint or.
Instruction * visitPtrToAddr(PtrToAddrInst &CI)
Instruction * visitInstruction(Instruction &I)
Specify what to return for unhandled instructions.
Instruction * foldSelectIntoOp(SelectInst &SI, Value *, Value *)
Try to fold the select into one of the operands to allow further optimization.
Instruction * foldShuffledIntrinsicOperands(IntrinsicInst *II)
If all arguments of the intrinsic are unary shuffles with the same mask, try to shuffle after the int...
Instruction * foldICmpAddConstant(ICmpInst &Cmp, BinaryOperator *Add, const APInt &C)
Fold icmp (add X, Y), C.
Instruction * foldICmpMulConstant(ICmpInst &Cmp, BinaryOperator *Mul, const APInt &C)
Fold icmp (mul X, Y), C.
Instruction * visitInvokeInst(InvokeInst &II)
Instruction * foldICmpCommutative(CmpPredicate Pred, Value *Op0, Value *Op1, ICmpInst &CtxI)
Instruction * tryFoldInstWithCtpopWithNot(Instruction *I)
Value * SimplifyDemandedUseBits(Instruction *I, const APInt &DemandedMask, KnownBits &Known, const SimplifyQuery &Q, unsigned Depth=0)
Attempts to replace I with a simpler value based on the demanded bits.
Instruction * foldVariableSignZeroExtensionOfVariableHighBitExtract(BinaryOperator &OldAShr)
Instruction * visitUncondBrInst(UncondBrInst &BI)
Instruction * commonShiftTransforms(BinaryOperator &I)
Instruction * visitFRem(BinaryOperator &I)
Instruction * foldPHIArgLoadIntoPHI(PHINode &PN)
Instruction * foldICmpXorConstant(ICmpInst &Cmp, BinaryOperator *Xor, const APInt &C)
Fold icmp (xor X, Y), C.
Instruction * FoldOrOfLogicalAnds(Value *Op0, Value *Op1)
Instruction * foldSelectICmp(CmpPredicate Pred, SelectInst *SI, Value *RHS, const ICmpInst &I)
bool foldIntegerTypedPHI(PHINode &PN)
If an integer typed PHI has only one use which is an IntToPtr operation, replace the PHI with an exis...
Instruction * foldICmpInstWithConstantAllowPoison(ICmpInst &Cmp, const APInt &C)
Try to fold integer comparisons with a constant operand: icmp Pred X, C where X is some kind of instr...
bool foldDeadPhiWeb(PHINode &PN)
If the phi is within a phi web, which is formed by the def-use chain of phis and all the phis in the ...
InstCombinerImpl(InstructionWorklist &Worklist, Function &F, AAResults *AA, AssumptionCache &AC, TargetLibraryInfo &TLI, TargetTransformInfo &TTI, DominatorTree &DT, OptimizationRemarkEmitter &ORE, BlockFrequencyInfo *BFI, BranchProbabilityInfo *BPI, ProfileSummaryInfo *PSI, const DataLayout &DL, ReversePostOrderTraversal< BasicBlock * > &RPOT, const InstCombineCLOptions &CLOpts)
Instruction * foldIsMultipleOfAPowerOfTwo(ICmpInst &Cmp)
Fold icmp eq (num + mask) & ~mask, num to icmp eq (and num, mask), 0 Where mask is a low bit mask.
Instruction * visitXor(BinaryOperator &I)
Value * foldSelectWithConstOpToBinOp(ICmpInst *Cmp, Value *TrueVal, Value *FalseVal)
Value * EvaluateInDifferentType(Value *V, Type *Ty, bool isSigned)
Given an expression that CanEvaluateTruncated or CanEvaluateSExtd returns true for,...
bool SimplifyDemandedInstructionBits(Instruction &Inst)
Tries to simplify operands to an integer instruction based on its demanded bits.
Instruction * simplifyBinOpSplats(ShuffleVectorInst &SVI)
void CreateNonTerminatorUnreachable(Instruction *InsertAt)
Create and insert the idiom we use to indicate a block is unreachable without having to rewrite the C...
Instruction * foldICmpAndShift(ICmpInst &Cmp, BinaryOperator *And, const APInt &C1, const APInt &C2)
Fold icmp (and (sh X, Y), C2), C1.
Value * pushFreezeToPreventPoisonFromPropagating(FreezeInst &FI)
Instruction * foldICmpBinOpWithConstantViaTruthTable(ICmpInst &Cmp, BinaryOperator *BO, const APInt &C)
Instruction * foldICmpInstWithConstant(ICmpInst &Cmp)
Try to fold integer comparisons with a constant operand: icmp Pred X, C where X is some kind of instr...
Instruction * visitSelectInst(SelectInst &SI)
Value * simplifyRangeCheck(CmpPredicate PredL, Value *LHS0, Value *LHS1, CmpPredicate PredR, Value *RHS0, Value *RHS1, Instruction *CtxI, bool Inverted)
Try to fold a signed range checked with lower bound 0 to an unsigned icmp.
Instruction * foldICmpXorShiftConst(ICmpInst &Cmp, BinaryOperator *Xor, const APInt &C)
For power-of-2 C: ((X s>> ShiftC) ^ X) u< C --> (X + C) u< (C << 1) ((X s>> ShiftC) ^ X) u> (C - 1) -...
Instruction * foldPHIArgIntToPtrToPHI(PHINode &PN)
Instruction * visitFPExt(CastInst &CI)
Instruction * foldICmpShlConstant(ICmpInst &Cmp, BinaryOperator *Shl, const APInt &C)
Fold icmp (shl X, Y), C.
Instruction * visitFMul(BinaryOperator &I)
Instruction * foldSelectOfBools(SelectInst &SI)
Instruction * foldSelectExtConst(SelectInst &Sel)
Instruction * foldAddWithConstant(BinaryOperator &Add)
Instruction * foldICmpAndConstant(ICmpInst &Cmp, BinaryOperator *And, const APInt &C)
Fold icmp (and X, Y), C.
bool run()
Run the combiner over the entire worklist until it is empty.
Instruction * foldFMulReassoc(BinaryOperator &I)
Instruction * SliceUpIllegalIntegerPHI(PHINode &PN)
This is an integer PHI and we know that it has an illegal type: see if it is only used by trunc or tr...
Instruction * foldAggregateConstructionIntoAggregateReuse(InsertValueInst &OrigIVI)
Look for chain of insertvalue's that fully define an aggregate, and trace back the values inserted,...
Instruction * foldICmpEquality(ICmpInst &Cmp)
Instruction * foldVectorBinop(BinaryOperator &Inst)
Canonicalize the position of binops relative to shufflevector.
bool removeInstructionsBeforeUnreachable(Instruction &I)
Instruction * foldPHIArgGEPIntoPHI(PHINode &PN)
Instruction * foldICmpWithMinMax(Instruction &I, MinMaxIntrinsic *MinMax, Value *Z, CmpPredicate Pred)
Fold icmp Pred min|max(X, Y), Z.
Instruction * visitShuffleVectorInst(ShuffleVectorInst &SVI)
Instruction * FoldShiftByConstant(Value *Op0, Constant *Op1, BinaryOperator &I)
void tryToSinkInstructionDbgVariableRecords(Instruction *I, BasicBlock::iterator InsertPos, BasicBlock *SrcBlock, BasicBlock *DestBlock, SmallVectorImpl< DbgVariableRecord * > &DPUsers)
bool foldAllocaCmp(AllocaInst *Alloca)
void addDeadEdge(BasicBlock *From, BasicBlock *To, SmallVectorImpl< BasicBlock * > &Worklist)
void PHIArgMergedDebugLoc(Instruction *Inst, PHINode &PN)
Helper function for FoldPHIArgXIntoPHI() to set debug location for the folded operation.
Instruction * visitVAEndInst(VAEndInst &I)
Value * SimplifyMultipleUseDemandedBits(Instruction *I, const APInt &DemandedMask, KnownBits &Known, const SimplifyQuery &Q, unsigned Depth=0)
Helper routine of SimplifyDemandedUseBits.
Instruction * matchBSwapOrBitReverse(Instruction &I, bool MatchBSwaps, bool MatchBitReversals)
Given an initial instruction, check to see if it is the root of a bswap/bitreverse idiom.
Constant * unshuffleConstant(ArrayRef< int > ShMask, Constant *C, VectorType *NewCTy)
Find a constant NewC that has property: shuffle(NewC, poison, ShMask) = C for lanes that select NewC.
Instruction * visitAllocSite(Instruction &FI)
Instruction * visitICmpInst(ICmpInst &I)
Instruction * SimplifyAnyMemTransfer(AnyMemTransferInst *MI)
Instruction * visitGetElementPtrInst(GetElementPtrInst &GEP)
Value * tryFactorizationFolds(BinaryOperator &I)
This tries to simplify binary operations by factorizing out common terms (e.
Instruction * foldPowiReassoc(BinaryOperator &I)
Instruction * foldFreezeIntoRecurrence(FreezeInst &I, PHINode *PN)
Instruction * visitSDiv(BinaryOperator &I)
bool tryToSinkInstruction(Instruction *I, BasicBlock *DestBlock)
Try to move the specified instruction from its current block into the beginning of DestBlock,...
Instruction * foldPHIArgExtractValueInstructionIntoPHI(PHINode &PN)
If we have something like phi [extractvalue(a,0), extractvalue(b,0)], turn this into a phi[a,...
Instruction * foldICmpShrConstConst(ICmpInst &I, Value *ShAmt, const APInt &C1, const APInt &C2)
Handle "(icmp eq/ne (ashr/lshr AP2, A), AP1)" -> (icmp eq/ne A, Log2(AP2/AP1)) -> (icmp eq/ne A,...
Instruction * visitFNeg(UnaryOperator &I)
void freelyInvertAllUsersOf(Value *V, Value *IgnoredUser=nullptr)
Freely adapt every user of V as-if V was changed to !V.
Instruction * commonIRemTransforms(BinaryOperator &I)
This function implements the transforms common to both integer remainder instructions (urem and srem)...
Instruction * visitAllocaInst(AllocaInst &AI)
Instruction * visitCallInst(CallInst &CI)
CallInst simplification.
Instruction * foldICmpAndConstConst(ICmpInst &Cmp, BinaryOperator *And, const APInt &C1)
Fold icmp (and X, C2), C1.
Instruction * visitFSub(BinaryOperator &I)
Instruction * foldICmpBitCast(ICmpInst &Cmp)
Instruction * foldGEPICmp(GEPOperator *GEPLHS, Value *RHS, CmpPredicate Cond, Instruction &I)
Fold comparisons between a GEP instruction and something else.
SimplifyQuery SQ
BlockFrequencyInfo * BFI
TargetLibraryInfo & TLI
InstructionWorklist & Worklist
A worklist of the instructions that need to be simplified.
Instruction * InsertNewInstWith(Instruction *New, BasicBlock::iterator Old)
Same as InsertNewInstBefore, but also sets the debug loc.
BranchProbabilityInfo * BPI
InstCombiner(InstructionWorklist &Worklist, Function &F, AAResults *AA, AssumptionCache &AC, TargetLibraryInfo &TLI, TargetTransformInfo &TTI, DominatorTree &DT, OptimizationRemarkEmitter &ORE, BlockFrequencyInfo *BFI, BranchProbabilityInfo *BPI, ProfileSummaryInfo *PSI, const DataLayout &DL, ReversePostOrderTraversal< BasicBlock * > &RPOT)
virtual bool SimplifyDemandedBits(Instruction *I, unsigned OpNo, const APInt &DemandedMask, KnownBits &Known, const SimplifyQuery &Q, unsigned Depth=0)=0
ReversePostOrderTraversal< BasicBlock * > & RPOT
const DataLayout & DL
DomConditionCache DC
AssumptionCache & AC
DominatorTree & DT
ProfileSummaryInfo * PSI
OptimizationRemarkEmitter & ORE
Base class for instruction visitors.
Definition InstVisitor.h:78
InstructionWorklist - This is the worklist management logic for InstCombine and other simplification ...
This class represents a cast from an integer to a pointer.
A wrapper class for inspecting calls to intrinsic functions.
Invoke instruction.
The landingpad instruction holds all of the information necessary to generate correct exception handl...
An instruction for reading from memory.
This class represents min/max intrinsics.
A Module instance is used to store all the information related to an LLVM module.
Definition Module.h:68
static Value * Negate(bool LHSIsZero, bool IsNSW, Value *Root, InstCombinerImpl &IC)
Attempt to negate Root.
The optimization diagnostic interface.
static PointerType * getUnqual(LLVMContext &C)
This constructs an opaque pointer to an object in the default address space (address space zero).
static LLVM_ABI PoisonValue * get(Type *T)
Static factory methods - Return an 'poison' object of the specified type.
Analysis providing profile information.
This class represents a cast from a pointer to an address (non-capturing ptrtoint).
This class represents a cast from a pointer to an integer.
Return a value (possibly void), from a function.
This class represents a sign extension of integer types.
This class represents the LLVM 'select' instruction.
This instruction constructs a fixed permutation of two input vectors.
This class consists of common code factored out of the SmallVector class to reduce code duplication b...
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
An instruction for storing to memory.
Multiway switch.
Provides information about what library functions are available for the current target.
This pass provides access to the codegen interfaces that are needed for IR-level transformations.
This class represents a truncation of integer types.
Twine - A lightweight data structure for efficiently representing the concatenation of temporary valu...
Definition Twine.h:82
The instances of the Type class are immutable: once they are created, they are never changed.
Definition Type.h:46
Unconditional Branch instruction.
This function has undefined behavior.
This represents the llvm.va_end intrinsic.
LLVM Value Representation.
Definition Value.h:75
LLVMContext & getContext() const
All values hold a context through their type.
Definition Value.h:260
Base class of all SIMD vector types.
This class represents zero extension of integer types.
self_iterator getIterator()
Definition ilist_node.h:123
CallInst * Call
#define llvm_unreachable(msg)
Marks that the current location is not supposed to be reachable.
friend class Instruction
Iterator for Instructions in a `BasicBlock.
Definition BasicBlock.h:73
This is an optimization pass for GlobalISel generic memory operations.
ShiftSemantics
Enum to specify how shift operations should be evaluated in canEvaluateShifted.
@ NeverOverflows
Never overflows.
@ Known
Known to have no common set bits.
LLVM_ABI void setExplicitlyUnknownBranchWeightsIfProfiled(Instruction &I, StringRef PassName, const Function *F=nullptr)
Like setExplicitlyUnknownBranchWeights(...), but only sets unknown branch weights in the new instruct...
LLVM_ABI void salvageDebugInfo(const MachineRegisterInfo &MRI, MachineInstr &MI)
Assuming the instruction MI is going to be deleted, attempt to salvage debug users of MI by writing t...
Definition Utils.cpp:1837
@ BinaryOp
One of the operands is a binary op.
LLVM_ABI OverflowResult computeOverflowForUnsignedMul(const Value *LHS, const Value *RHS, const SimplifyQuery &SQ, bool IsNSW=false)
LLVM_ABI OverflowResult computeOverflowForSignedSub(const Value *LHS, const Value *RHS, const SimplifyQuery &SQ)
SelectPatternFlavor
Specific patterns of select instructions we can match.
FPClassTest
Floating-point class tests, supported by 'is_fpclass' intrinsic.
LLVM_ABI raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
Definition Debug.cpp:209
LLVM_ABI OverflowResult computeOverflowForSignedMul(const Value *LHS, const Value *RHS, const SimplifyQuery &SQ)
TargetTransformInfo TTI
@ Mul
Product of integers.
@ Xor
Bitwise or logical XOR of integers.
@ Sub
Subtraction of integers.
@ Add
Sum of integers.
DWARFExpression::Operation Op
constexpr unsigned BitWidth
LLVM_ABI OverflowResult computeOverflowForUnsignedSub(const Value *LHS, const Value *RHS, const SimplifyQuery &SQ)
LLVM_ABI OverflowResult computeOverflowForUnsignedAdd(const WithCache< const Value * > &LHS, const WithCache< const Value * > &RHS, const SimplifyQuery &SQ)
This struct is a compact representation of a valid (non-zero power of two) alignment.
Definition Alignment.h:39
Value * Ptr
Common base pointer.
SmallVector< GEPOperator * > RHSGEPs
RHS GEPs until common base.
GEPNoWrapFlags LHSNW
LHS GEP NoWrapFlags until common base.
GEPNoWrapFlags RHSNW
RHS GEP NoWrapFlags until common base.
SmallVector< GEPOperator * > LHSGEPs
LHS GEPs until common base.
bool isExpensive() const
Whether expanding the GEP chains is expensive.
static CommonPointerBase compute(Value *LHS, Value *RHS)
Matching combinators.