blob: f4e88b122383186d8c3b636a628e9a694bbc66f5 [file] [log] [blame]
//===- InstCombineInternal.h - InstCombine pass internals -------*- C++ -*-===//
//
// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
// See https://llvm.org/LICENSE.txt for license information.
// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
//
//===----------------------------------------------------------------------===//
//
/// \file
///
/// This file provides internal interfaces used to implement the InstCombine.
//
//===----------------------------------------------------------------------===//
#ifndef LLVM_LIB_TRANSFORMS_INSTCOMBINE_INSTCOMBINEINTERNAL_H
#define LLVM_LIB_TRANSFORMS_INSTCOMBINE_INSTCOMBINEINTERNAL_H
#include "llvm/ADT/Statistic.h"
#include "llvm/Analysis/InstructionSimplify.h"
#include "llvm/Analysis/TargetFolder.h"
#include "llvm/Analysis/ValueTracking.h"
#include "llvm/IR/IRBuilder.h"
#include "llvm/IR/InstVisitor.h"
#include "llvm/IR/PatternMatch.h"
#include "llvm/IR/Value.h"
#include "llvm/Support/Debug.h"
#include "llvm/Support/KnownBits.h"
#include "llvm/Transforms/InstCombine/InstCombiner.h"
#include "llvm/Transforms/Utils/Local.h"
#include <cassert>
#define DEBUG_TYPE "instcombine"
#include "llvm/Transforms/Utils/InstructionWorklist.h"
using namespace llvm::PatternMatch;
// As a default, let's assume that we want to be aggressive,
// and attempt to traverse with no limits in attempt to sink negation.
static constexpr unsigned NegatorDefaultMaxDepth = ~0U;
// Let's guesstimate that most often we will end up visiting/producing
// fairly small number of new instructions.
static constexpr unsigned NegatorMaxNodesSSO = 16;
namespace llvm {
class AAResults;
class APInt;
class AssumptionCache;
class BlockFrequencyInfo;
class DataLayout;
class DominatorTree;
class GEPOperator;
class GlobalVariable;
class LoopInfo;
class OptimizationRemarkEmitter;
class ProfileSummaryInfo;
class TargetLibraryInfo;
class User;
class LLVM_LIBRARY_VISIBILITY InstCombinerImpl final
: public InstCombiner,
public InstVisitor<InstCombinerImpl, Instruction *> {
public:
InstCombinerImpl(InstructionWorklist &Worklist, BuilderTy &Builder,
bool MinimizeSize, AAResults *AA, AssumptionCache &AC,
TargetLibraryInfo &TLI, TargetTransformInfo &TTI,
DominatorTree &DT, OptimizationRemarkEmitter &ORE,
BlockFrequencyInfo *BFI, ProfileSummaryInfo *PSI,
const DataLayout &DL, LoopInfo *LI)
: InstCombiner(Worklist, Builder, MinimizeSize, AA, AC, TLI, TTI, DT, ORE,
BFI, PSI, DL, LI) {}
virtual ~InstCombinerImpl() = default;
/// Run the combiner over the entire worklist until it is empty.
///
/// \returns true if the IR is changed.
bool run();
// Visitation implementation - Implement instruction combining for different
// instruction types. The semantics are as follows:
// Return Value:
// null - No change was made
// I - Change was made, I is still valid, I may be dead though
// otherwise - Change was made, replace I with returned instruction
//
Instruction *visitFNeg(UnaryOperator &I);
Instruction *visitAdd(BinaryOperator &I);
Instruction *visitFAdd(BinaryOperator &I);
Value *OptimizePointerDifference(
Value *LHS, Value *RHS, Type *Ty, bool isNUW);
Instruction *visitSub(BinaryOperator &I);
Instruction *visitFSub(BinaryOperator &I);
Instruction *visitMul(BinaryOperator &I);
Instruction *visitFMul(BinaryOperator &I);
Instruction *visitURem(BinaryOperator &I);
Instruction *visitSRem(BinaryOperator &I);
Instruction *visitFRem(BinaryOperator &I);
bool simplifyDivRemOfSelectWithZeroOp(BinaryOperator &I);
Instruction *commonIRemTransforms(BinaryOperator &I);
Instruction *commonIDivTransforms(BinaryOperator &I);
Instruction *visitUDiv(BinaryOperator &I);
Instruction *visitSDiv(BinaryOperator &I);
Instruction *visitFDiv(BinaryOperator &I);
Value *simplifyRangeCheck(ICmpInst *Cmp0, ICmpInst *Cmp1, bool Inverted);
Instruction *visitAnd(BinaryOperator &I);
Instruction *visitOr(BinaryOperator &I);
bool sinkNotIntoLogicalOp(Instruction &I);
bool sinkNotIntoOtherHandOfLogicalOp(Instruction &I);
Instruction *visitXor(BinaryOperator &I);
Instruction *visitShl(BinaryOperator &I);
Value *reassociateShiftAmtsOfTwoSameDirectionShifts(
BinaryOperator *Sh0, const SimplifyQuery &SQ,
bool AnalyzeForSignBitExtraction = false);
Instruction *canonicalizeCondSignextOfHighBitExtractToSignextHighBitExtract(
BinaryOperator &I);
Instruction *foldVariableSignZeroExtensionOfVariableHighBitExtract(
BinaryOperator &OldAShr);
Instruction *visitAShr(BinaryOperator &I);
Instruction *visitLShr(BinaryOperator &I);
Instruction *commonShiftTransforms(BinaryOperator &I);
Instruction *visitFCmpInst(FCmpInst &I);
CmpInst *canonicalizeICmpPredicate(CmpInst &I);
Instruction *visitICmpInst(ICmpInst &I);
Instruction *FoldShiftByConstant(Value *Op0, Constant *Op1,
BinaryOperator &I);
Instruction *commonCastTransforms(CastInst &CI);
Instruction *commonPointerCastTransforms(CastInst &CI);
Instruction *visitTrunc(TruncInst &CI);
Instruction *visitZExt(ZExtInst &Zext);
Instruction *visitSExt(SExtInst &Sext);
Instruction *visitFPTrunc(FPTruncInst &CI);
Instruction *visitFPExt(CastInst &CI);
Instruction *visitFPToUI(FPToUIInst &FI);
Instruction *visitFPToSI(FPToSIInst &FI);
Instruction *visitUIToFP(CastInst &CI);
Instruction *visitSIToFP(CastInst &CI);
Instruction *visitPtrToInt(PtrToIntInst &CI);
Instruction *visitIntToPtr(IntToPtrInst &CI);
Instruction *visitBitCast(BitCastInst &CI);
Instruction *visitAddrSpaceCast(AddrSpaceCastInst &CI);
Instruction *foldItoFPtoI(CastInst &FI);
Instruction *visitSelectInst(SelectInst &SI);
Instruction *visitCallInst(CallInst &CI);
Instruction *visitInvokeInst(InvokeInst &II);
Instruction *visitCallBrInst(CallBrInst &CBI);
Instruction *SliceUpIllegalIntegerPHI(PHINode &PN);
Instruction *visitPHINode(PHINode &PN);
Instruction *visitGetElementPtrInst(GetElementPtrInst &GEP);
Instruction *visitGEPOfGEP(GetElementPtrInst &GEP, GEPOperator *Src);
Instruction *visitGEPOfBitcast(BitCastInst *BCI, GetElementPtrInst &GEP);
Instruction *visitAllocaInst(AllocaInst &AI);
Instruction *visitAllocSite(Instruction &FI);
Instruction *visitFree(CallInst &FI, Value *FreedOp);
Instruction *visitLoadInst(LoadInst &LI);
Instruction *visitStoreInst(StoreInst &SI);
Instruction *visitAtomicRMWInst(AtomicRMWInst &SI);
Instruction *visitUnconditionalBranchInst(BranchInst &BI);
Instruction *visitBranchInst(BranchInst &BI);
Instruction *visitFenceInst(FenceInst &FI);
Instruction *visitSwitchInst(SwitchInst &SI);
Instruction *visitReturnInst(ReturnInst &RI);
Instruction *visitUnreachableInst(UnreachableInst &I);
Instruction *
foldAggregateConstructionIntoAggregateReuse(InsertValueInst &OrigIVI);
Instruction *visitInsertValueInst(InsertValueInst &IV);
Instruction *visitInsertElementInst(InsertElementInst &IE);
Instruction *visitExtractElementInst(ExtractElementInst &EI);
Instruction *simplifyBinOpSplats(ShuffleVectorInst &SVI);
Instruction *visitShuffleVectorInst(ShuffleVectorInst &SVI);
Instruction *visitExtractValueInst(ExtractValueInst &EV);
Instruction *visitLandingPadInst(LandingPadInst &LI);
Instruction *visitVAEndInst(VAEndInst &I);
Value *pushFreezeToPreventPoisonFromPropagating(FreezeInst &FI);
bool freezeOtherUses(FreezeInst &FI);
Instruction *foldFreezeIntoRecurrence(FreezeInst &I, PHINode *PN);
Instruction *visitFreeze(FreezeInst &I);
/// Specify what to return for unhandled instructions.
Instruction *visitInstruction(Instruction &I) { return nullptr; }
/// True when DB dominates all uses of DI except UI.
/// UI must be in the same block as DI.
/// The routine checks that the DI parent and DB are different.
bool dominatesAllUses(const Instruction *DI, const Instruction *UI,
const BasicBlock *DB) const;
/// Try to replace select with select operand SIOpd in SI-ICmp sequence.
bool replacedSelectWithOperand(SelectInst *SI, const ICmpInst *Icmp,
const unsigned SIOpd);
LoadInst *combineLoadToNewType(LoadInst &LI, Type *NewTy,
const Twine &Suffix = "");
private:
bool annotateAnyAllocSite(CallBase &Call, const TargetLibraryInfo *TLI);
bool isDesirableIntType(unsigned BitWidth) const;
bool shouldChangeType(unsigned FromBitWidth, unsigned ToBitWidth) const;
bool shouldChangeType(Type *From, Type *To) const;
Value *dyn_castNegVal(Value *V) const;
/// Classify whether a cast is worth optimizing.
///
/// This is a helper to decide whether the simplification of
/// logic(cast(A), cast(B)) to cast(logic(A, B)) should be performed.
///
/// \param CI The cast we are interested in.
///
/// \return true if this cast actually results in any code being generated and
/// if it cannot already be eliminated by some other transformation.
bool shouldOptimizeCast(CastInst *CI);
/// Try to optimize a sequence of instructions checking if an operation
/// on LHS and RHS overflows.
///
/// If this overflow check is done via one of the overflow check intrinsics,
/// then CtxI has to be the call instruction calling that intrinsic. If this
/// overflow check is done by arithmetic followed by a compare, then CtxI has
/// to be the arithmetic instruction.
///
/// If a simplification is possible, stores the simplified result of the
/// operation in OperationResult and result of the overflow check in
/// OverflowResult, and return true. If no simplification is possible,
/// returns false.
bool OptimizeOverflowCheck(Instruction::BinaryOps BinaryOp, bool IsSigned,
Value *LHS, Value *RHS,
Instruction &CtxI, Value *&OperationResult,
Constant *&OverflowResult);
Instruction *visitCallBase(CallBase &Call);
Instruction *tryOptimizeCall(CallInst *CI);
bool transformConstExprCastCall(CallBase &Call);
Instruction *transformCallThroughTrampoline(CallBase &Call,
IntrinsicInst &Tramp);
Value *simplifyMaskedLoad(IntrinsicInst &II);
Instruction *simplifyMaskedStore(IntrinsicInst &II);
Instruction *simplifyMaskedGather(IntrinsicInst &II);
Instruction *simplifyMaskedScatter(IntrinsicInst &II);
/// Transform (zext icmp) to bitwise / integer operations in order to
/// eliminate it.
///
/// \param ICI The icmp of the (zext icmp) pair we are interested in.
/// \parem CI The zext of the (zext icmp) pair we are interested in.
///
/// \return null if the transformation cannot be performed. If the
/// transformation can be performed the new instruction that replaces the
/// (zext icmp) pair will be returned.
Instruction *transformZExtICmp(ICmpInst *Cmp, ZExtInst &Zext);
Instruction *transformSExtICmp(ICmpInst *Cmp, SExtInst &Sext);
bool willNotOverflowSignedAdd(const Value *LHS, const Value *RHS,
const Instruction &CxtI) const {
return computeOverflowForSignedAdd(LHS, RHS, &CxtI) ==
OverflowResult::NeverOverflows;
}
bool willNotOverflowUnsignedAdd(const Value *LHS, const Value *RHS,
const Instruction &CxtI) const {
return computeOverflowForUnsignedAdd(LHS, RHS, &CxtI) ==
OverflowResult::NeverOverflows;
}
bool willNotOverflowAdd(const Value *LHS, const Value *RHS,
const Instruction &CxtI, bool IsSigned) const {
return IsSigned ? willNotOverflowSignedAdd(LHS, RHS, CxtI)
: willNotOverflowUnsignedAdd(LHS, RHS, CxtI);
}
bool willNotOverflowSignedSub(const Value *LHS, const Value *RHS,
const Instruction &CxtI) const {
return computeOverflowForSignedSub(LHS, RHS, &CxtI) ==
OverflowResult::NeverOverflows;
}
bool willNotOverflowUnsignedSub(const Value *LHS, const Value *RHS,
const Instruction &CxtI) const {
return computeOverflowForUnsignedSub(LHS, RHS, &CxtI) ==
OverflowResult::NeverOverflows;
}
bool willNotOverflowSub(const Value *LHS, const Value *RHS,
const Instruction &CxtI, bool IsSigned) const {
return IsSigned ? willNotOverflowSignedSub(LHS, RHS, CxtI)
: willNotOverflowUnsignedSub(LHS, RHS, CxtI);
}
bool willNotOverflowSignedMul(const Value *LHS, const Value *RHS,
const Instruction &CxtI) const {
return computeOverflowForSignedMul(LHS, RHS, &CxtI) ==
OverflowResult::NeverOverflows;
}
bool willNotOverflowUnsignedMul(const Value *LHS, const Value *RHS,
const Instruction &CxtI) const {
return computeOverflowForUnsignedMul(LHS, RHS, &CxtI) ==
OverflowResult::NeverOverflows;
}
bool willNotOverflowMul(const Value *LHS, const Value *RHS,
const Instruction &CxtI, bool IsSigned) const {
return IsSigned ? willNotOverflowSignedMul(LHS, RHS, CxtI)
: willNotOverflowUnsignedMul(LHS, RHS, CxtI);
}
bool willNotOverflow(BinaryOperator::BinaryOps Opcode, const Value *LHS,
const Value *RHS, const Instruction &CxtI,
bool IsSigned) const {
switch (Opcode) {
case Instruction::Add: return willNotOverflowAdd(LHS, RHS, CxtI, IsSigned);
case Instruction::Sub: return willNotOverflowSub(LHS, RHS, CxtI, IsSigned);
case Instruction::Mul: return willNotOverflowMul(LHS, RHS, CxtI, IsSigned);
default: llvm_unreachable("Unexpected opcode for overflow query");
}
}
Value *EmitGEPOffset(User *GEP);
Instruction *scalarizePHI(ExtractElementInst &EI, PHINode *PN);
Instruction *foldBitcastExtElt(ExtractElementInst &ExtElt);
Instruction *foldCastedBitwiseLogic(BinaryOperator &I);
Instruction *foldBinopOfSextBoolToSelect(BinaryOperator &I);
Instruction *narrowBinOp(TruncInst &Trunc);
Instruction *narrowMaskedBinOp(BinaryOperator &And);
Instruction *narrowMathIfNoOverflow(BinaryOperator &I);
Instruction *narrowFunnelShift(TruncInst &Trunc);
Instruction *optimizeBitCastFromPhi(CastInst &CI, PHINode *PN);
Instruction *matchSAddSubSat(IntrinsicInst &MinMax1);
Instruction *foldNot(BinaryOperator &I);
void freelyInvertAllUsersOf(Value *V, Value *IgnoredUser = nullptr);
/// Determine if a pair of casts can be replaced by a single cast.
///
/// \param CI1 The first of a pair of casts.
/// \param CI2 The second of a pair of casts.
///
/// \return 0 if the cast pair cannot be eliminated, otherwise returns an
/// Instruction::CastOps value for a cast that can replace the pair, casting
/// CI1->getSrcTy() to CI2->getDstTy().
///
/// \see CastInst::isEliminableCastPair
Instruction::CastOps isEliminableCastPair(const CastInst *CI1,
const CastInst *CI2);
Value *simplifyIntToPtrRoundTripCast(Value *Val);
Value *foldAndOrOfICmps(ICmpInst *LHS, ICmpInst *RHS, Instruction &I,
bool IsAnd, bool IsLogical = false);
Value *foldXorOfICmps(ICmpInst *LHS, ICmpInst *RHS, BinaryOperator &Xor);
Value *foldEqOfParts(ICmpInst *Cmp0, ICmpInst *Cmp1, bool IsAnd);
Value *foldAndOrOfICmpsUsingRanges(ICmpInst *ICmp1, ICmpInst *ICmp2,
bool IsAnd);
/// Optimize (fcmp)&(fcmp) or (fcmp)|(fcmp).
/// NOTE: Unlike most of instcombine, this returns a Value which should
/// already be inserted into the function.
Value *foldLogicOfFCmps(FCmpInst *LHS, FCmpInst *RHS, bool IsAnd,
bool IsLogicalSelect = false);
Instruction *foldLogicOfIsFPClass(BinaryOperator &Operator, Value *LHS,
Value *RHS);
Instruction *
canonicalizeConditionalNegationViaMathToSelect(BinaryOperator &i);
Value *foldAndOrOfICmpsOfAndWithPow2(ICmpInst *LHS, ICmpInst *RHS,
Instruction *CxtI, bool IsAnd,
bool IsLogical = false);
Value *matchSelectFromAndOr(Value *A, Value *B, Value *C, Value *D,
bool InvertFalseVal = false);
Value *getSelectCondition(Value *A, Value *B, bool ABIsTheSame);
Instruction *foldLShrOverflowBit(BinaryOperator &I);
Instruction *foldExtractOfOverflowIntrinsic(ExtractValueInst &EV);
Instruction *foldIntrinsicWithOverflowCommon(IntrinsicInst *II);
Instruction *foldFPSignBitOps(BinaryOperator &I);
Instruction *foldFDivConstantDivisor(BinaryOperator &I);
// Optimize one of these forms:
// and i1 Op, SI / select i1 Op, i1 SI, i1 false (if IsAnd = true)
// or i1 Op, SI / select i1 Op, i1 true, i1 SI (if IsAnd = false)
// into simplier select instruction using isImpliedCondition.
Instruction *foldAndOrOfSelectUsingImpliedCond(Value *Op, SelectInst &SI,
bool IsAnd);
public:
/// Create and insert the idiom we use to indicate a block is unreachable
/// without having to rewrite the CFG from within InstCombine.
void CreateNonTerminatorUnreachable(Instruction *InsertAt) {
auto &Ctx = InsertAt->getContext();
new StoreInst(ConstantInt::getTrue(Ctx),
PoisonValue::get(Type::getInt1PtrTy(Ctx)),
InsertAt);
}
/// Combiner aware instruction erasure.
///
/// When dealing with an instruction that has side effects or produces a void
/// value, we can't rely on DCE to delete the instruction. Instead, visit
/// methods should return the value returned by this function.
Instruction *eraseInstFromFunction(Instruction &I) override {
LLVM_DEBUG(dbgs() << "IC: ERASE " << I << '\n');
assert(I.use_empty() && "Cannot erase instruction that is used!");
salvageDebugInfo(I);
// Make sure that we reprocess all operands now that we reduced their
// use counts.
for (Use &Operand : I.operands())
if (auto *Inst = dyn_cast<Instruction>(Operand))
Worklist.add(Inst);
Worklist.remove(&I);
I.eraseFromParent();
MadeIRChange = true;
return nullptr; // Don't do anything with FI
}
OverflowResult computeOverflow(
Instruction::BinaryOps BinaryOp, bool IsSigned,
Value *LHS, Value *RHS, Instruction *CxtI) const;
/// Performs a few simplifications for operators which are associative
/// or commutative.
bool SimplifyAssociativeOrCommutative(BinaryOperator &I);
/// Tries to simplify binary operations which some other binary
/// operation distributes over.
///
/// It does this by either by factorizing out common terms (eg "(A*B)+(A*C)"
/// -> "A*(B+C)") or expanding out if this results in simplifications (eg: "A
/// & (B | C) -> (A&B) | (A&C)" if this is a win). Returns the simplified
/// value, or null if it didn't simplify.
Value *foldUsingDistributiveLaws(BinaryOperator &I);
/// Tries to simplify add operations using the definition of remainder.
///
/// The definition of remainder is X % C = X - (X / C ) * C. The add
/// expression X % C0 + (( X / C0 ) % C1) * C0 can be simplified to
/// X % (C0 * C1)
Value *SimplifyAddWithRemainder(BinaryOperator &I);
// Binary Op helper for select operations where the expression can be
// efficiently reorganized.
Value *SimplifySelectsFeedingBinaryOp(BinaryOperator &I, Value *LHS,
Value *RHS);
/// This tries to simplify binary operations by factorizing out common terms
/// (e. g. "(A*B)+(A*C)" -> "A*(B+C)").
Value *tryFactorizationFolds(BinaryOperator &I);
/// Match a select chain which produces one of three values based on whether
/// the LHS is less than, equal to, or greater than RHS respectively.
/// Return true if we matched a three way compare idiom. The LHS, RHS, Less,
/// Equal and Greater values are saved in the matching process and returned to
/// the caller.
bool matchThreeWayIntCompare(SelectInst *SI, Value *&LHS, Value *&RHS,
ConstantInt *&Less, ConstantInt *&Equal,
ConstantInt *&Greater);
/// Attempts to replace V with a simpler value based on the demanded
/// bits.
Value *SimplifyDemandedUseBits(Value *V, APInt DemandedMask, KnownBits &Known,
unsigned Depth, Instruction *CxtI);
bool SimplifyDemandedBits(Instruction *I, unsigned Op,
const APInt &DemandedMask, KnownBits &Known,
unsigned Depth = 0) override;
/// Helper routine of SimplifyDemandedUseBits. It computes KnownZero/KnownOne
/// bits. It also tries to handle simplifications that can be done based on
/// DemandedMask, but without modifying the Instruction.
Value *SimplifyMultipleUseDemandedBits(Instruction *I,
const APInt &DemandedMask,
KnownBits &Known,
unsigned Depth, Instruction *CxtI);
/// Helper routine of SimplifyDemandedUseBits. It tries to simplify demanded
/// bit for "r1 = shr x, c1; r2 = shl r1, c2" instruction sequence.
Value *simplifyShrShlDemandedBits(
Instruction *Shr, const APInt &ShrOp1, Instruction *Shl,
const APInt &ShlOp1, const APInt &DemandedMask, KnownBits &Known);
/// Tries to simplify operands to an integer instruction based on its
/// demanded bits.
bool SimplifyDemandedInstructionBits(Instruction &Inst);
Value *SimplifyDemandedVectorElts(Value *V, APInt DemandedElts,
APInt &UndefElts, unsigned Depth = 0,
bool AllowMultipleUsers = false) override;
/// Canonicalize the position of binops relative to shufflevector.
Instruction *foldVectorBinop(BinaryOperator &Inst);
Instruction *foldVectorSelect(SelectInst &Sel);
Instruction *foldSelectShuffle(ShuffleVectorInst &Shuf);
/// Given a binary operator, cast instruction, or select which has a PHI node
/// as operand #0, see if we can fold the instruction into the PHI (which is
/// only possible if all operands to the PHI are constants).
Instruction *foldOpIntoPhi(Instruction &I, PHINode *PN);
/// For a binary operator with 2 phi operands, try to hoist the binary
/// operation before the phi. This can result in fewer instructions in
/// patterns where at least one set of phi operands simplifies.
/// Example:
/// BB3: binop (phi [X, BB1], [C1, BB2]), (phi [Y, BB1], [C2, BB2])
/// -->
/// BB1: BO = binop X, Y
/// BB3: phi [BO, BB1], [(binop C1, C2), BB2]
Instruction *foldBinopWithPhiOperands(BinaryOperator &BO);
/// Given an instruction with a select as one operand and a constant as the
/// other operand, try to fold the binary operator into the select arguments.
/// This also works for Cast instructions, which obviously do not have a
/// second operand.
Instruction *FoldOpIntoSelect(Instruction &Op, SelectInst *SI,
bool FoldWithMultiUse = false);
/// This is a convenience wrapper function for the above two functions.
Instruction *foldBinOpIntoSelectOrPhi(BinaryOperator &I);
Instruction *foldAddWithConstant(BinaryOperator &Add);
/// Try to rotate an operation below a PHI node, using PHI nodes for
/// its operands.
Instruction *foldPHIArgOpIntoPHI(PHINode &PN);
Instruction *foldPHIArgBinOpIntoPHI(PHINode &PN);
Instruction *foldPHIArgInsertValueInstructionIntoPHI(PHINode &PN);
Instruction *foldPHIArgExtractValueInstructionIntoPHI(PHINode &PN);
Instruction *foldPHIArgGEPIntoPHI(PHINode &PN);
Instruction *foldPHIArgLoadIntoPHI(PHINode &PN);
Instruction *foldPHIArgZextsIntoPHI(PHINode &PN);
Instruction *foldPHIArgIntToPtrToPHI(PHINode &PN);
/// If an integer typed PHI has only one use which is an IntToPtr operation,
/// replace the PHI with an existing pointer typed PHI if it exists. Otherwise
/// insert a new pointer typed PHI and replace the original one.
bool foldIntegerTypedPHI(PHINode &PN);
/// Helper function for FoldPHIArgXIntoPHI() to set debug location for the
/// folded operation.
void PHIArgMergedDebugLoc(Instruction *Inst, PHINode &PN);
Instruction *foldGEPICmp(GEPOperator *GEPLHS, Value *RHS,
ICmpInst::Predicate Cond, Instruction &I);
Instruction *foldSelectICmp(ICmpInst::Predicate Pred, SelectInst *SI,
Value *RHS, const ICmpInst &I);
Instruction *foldAllocaCmp(ICmpInst &ICI, const AllocaInst *Alloca);
Instruction *foldCmpLoadFromIndexedGlobal(LoadInst *LI,
GetElementPtrInst *GEP,
GlobalVariable *GV, CmpInst &ICI,
ConstantInt *AndCst = nullptr);
Instruction *foldFCmpIntToFPConst(FCmpInst &I, Instruction *LHSI,
Constant *RHSC);
Instruction *foldICmpAddOpConst(Value *X, const APInt &C,
ICmpInst::Predicate Pred);
Instruction *foldICmpWithCastOp(ICmpInst &ICmp);
Instruction *foldICmpWithZextOrSext(ICmpInst &ICmp);
Instruction *foldICmpUsingKnownBits(ICmpInst &Cmp);
Instruction *foldICmpWithDominatingICmp(ICmpInst &Cmp);
Instruction *foldICmpWithConstant(ICmpInst &Cmp);
Instruction *foldICmpInstWithConstant(ICmpInst &Cmp);
Instruction *foldICmpInstWithConstantNotInt(ICmpInst &Cmp);
Instruction *foldICmpInstWithConstantAllowUndef(ICmpInst &Cmp,
const APInt &C);
Instruction *foldICmpBinOp(ICmpInst &Cmp, const SimplifyQuery &SQ);
Instruction *foldICmpEquality(ICmpInst &Cmp);
Instruction *foldIRemByPowerOfTwoToBitTest(ICmpInst &I);
Instruction *foldSignBitTest(ICmpInst &I);
Instruction *foldICmpWithZero(ICmpInst &Cmp);
Value *foldMultiplicationOverflowCheck(ICmpInst &Cmp);
Instruction *foldICmpBinOpWithConstant(ICmpInst &Cmp, BinaryOperator *BO,
const APInt &C);
Instruction *foldICmpSelectConstant(ICmpInst &Cmp, SelectInst *Select,
ConstantInt *C);
Instruction *foldICmpTruncConstant(ICmpInst &Cmp, TruncInst *Trunc,
const APInt &C);
Instruction *foldICmpAndConstant(ICmpInst &Cmp, BinaryOperator *And,
const APInt &C);
Instruction *foldICmpXorConstant(ICmpInst &Cmp, BinaryOperator *Xor,
const APInt &C);
Instruction *foldICmpOrConstant(ICmpInst &Cmp, BinaryOperator *Or,
const APInt &C);
Instruction *foldICmpMulConstant(ICmpInst &Cmp, BinaryOperator *Mul,
const APInt &C);
Instruction *foldICmpShlConstant(ICmpInst &Cmp, BinaryOperator *Shl,
const APInt &C);
Instruction *foldICmpShrConstant(ICmpInst &Cmp, BinaryOperator *Shr,
const APInt &C);
Instruction *foldICmpSRemConstant(ICmpInst &Cmp, BinaryOperator *UDiv,
const APInt &C);
Instruction *foldICmpUDivConstant(ICmpInst &Cmp, BinaryOperator *UDiv,
const APInt &C);
Instruction *foldICmpDivConstant(ICmpInst &Cmp, BinaryOperator *Div,
const APInt &C);
Instruction *foldICmpSubConstant(ICmpInst &Cmp, BinaryOperator *Sub,
const APInt &C);
Instruction *foldICmpAddConstant(ICmpInst &Cmp, BinaryOperator *Add,
const APInt &C);
Instruction *foldICmpAndConstConst(ICmpInst &Cmp, BinaryOperator *And,
const APInt &C1);
Instruction *foldICmpAndShift(ICmpInst &Cmp, BinaryOperator *And,
const APInt &C1, const APInt &C2);
Instruction *foldICmpXorShiftConst(ICmpInst &Cmp, BinaryOperator *Xor,
const APInt &C);
Instruction *foldICmpShrConstConst(ICmpInst &I, Value *ShAmt, const APInt &C1,
const APInt &C2);
Instruction *foldICmpShlConstConst(ICmpInst &I, Value *ShAmt, const APInt &C1,
const APInt &C2);
Instruction *foldICmpBinOpEqualityWithConstant(ICmpInst &Cmp,
BinaryOperator *BO,
const APInt &C);
Instruction *foldICmpIntrinsicWithConstant(ICmpInst &ICI, IntrinsicInst *II,
const APInt &C);
Instruction *foldICmpEqIntrinsicWithConstant(ICmpInst &ICI, IntrinsicInst *II,
const APInt &C);
Instruction *foldICmpBitCast(ICmpInst &Cmp);
// Helpers of visitSelectInst().
Instruction *foldSelectOfBools(SelectInst &SI);
Instruction *foldSelectExtConst(SelectInst &Sel);
Instruction *foldSelectOpOp(SelectInst &SI, Instruction *TI, Instruction *FI);
Instruction *foldSelectIntoOp(SelectInst &SI, Value *, Value *);
Instruction *foldSPFofSPF(Instruction *Inner, SelectPatternFlavor SPF1,
Value *A, Value *B, Instruction &Outer,
SelectPatternFlavor SPF2, Value *C);
Instruction *foldSelectInstWithICmp(SelectInst &SI, ICmpInst *ICI);
Instruction *foldSelectValueEquivalence(SelectInst &SI, ICmpInst &ICI);
Value *insertRangeTest(Value *V, const APInt &Lo, const APInt &Hi,
bool isSigned, bool Inside);
Instruction *PromoteCastOfAllocation(BitCastInst &CI, AllocaInst &AI);
bool mergeStoreIntoSuccessor(StoreInst &SI);
/// Given an initial instruction, check to see if it is the root of a
/// bswap/bitreverse idiom. If so, return the equivalent bswap/bitreverse
/// intrinsic.
Instruction *matchBSwapOrBitReverse(Instruction &I, bool MatchBSwaps,
bool MatchBitReversals);
Instruction *SimplifyAnyMemTransfer(AnyMemTransferInst *MI);
Instruction *SimplifyAnyMemSet(AnyMemSetInst *MI);
Value *EvaluateInDifferentType(Value *V, Type *Ty, bool isSigned);
/// Returns a value X such that Val = X * Scale, or null if none.
///
/// If the multiplication is known not to overflow then NoSignedWrap is set.
Value *Descale(Value *Val, APInt Scale, bool &NoSignedWrap);
};
class Negator final {
/// Top-to-bottom, def-to-use negated instruction tree we produced.
SmallVector<Instruction *, NegatorMaxNodesSSO> NewInstructions;
using BuilderTy = IRBuilder<TargetFolder, IRBuilderCallbackInserter>;
BuilderTy Builder;
const DataLayout &DL;
AssumptionCache &AC;
const DominatorTree &DT;
const bool IsTrulyNegation;
SmallDenseMap<Value *, Value *> NegationsCache;
Negator(LLVMContext &C, const DataLayout &DL, AssumptionCache &AC,
const DominatorTree &DT, bool IsTrulyNegation);
#if LLVM_ENABLE_STATS
unsigned NumValuesVisitedInThisNegator = 0;
~Negator();
#endif
using Result = std::pair<ArrayRef<Instruction *> /*NewInstructions*/,
Value * /*NegatedRoot*/>;
std::array<Value *, 2> getSortedOperandsOfBinOp(Instruction *I);
[[nodiscard]] Value *visitImpl(Value *V, unsigned Depth);
[[nodiscard]] Value *negate(Value *V, unsigned Depth);
/// Recurse depth-first and attempt to sink the negation.
/// FIXME: use worklist?
[[nodiscard]] std::optional<Result> run(Value *Root);
Negator(const Negator &) = delete;
Negator(Negator &&) = delete;
Negator &operator=(const Negator &) = delete;
Negator &operator=(Negator &&) = delete;
public:
/// Attempt to negate \p Root. Retuns nullptr if negation can't be performed,
/// otherwise returns negated value.
[[nodiscard]] static Value *Negate(bool LHSIsZero, Value *Root,
InstCombinerImpl &IC);
};
} // end namespace llvm
#undef DEBUG_TYPE
#endif // LLVM_LIB_TRANSFORMS_INSTCOMBINE_INSTCOMBINEINTERNAL_H