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