173471bf0Spatrick //===- InstCombiner.h - InstCombine implementation --------------*- C++ -*-===// 273471bf0Spatrick // 373471bf0Spatrick // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. 473471bf0Spatrick // See https://llvm.org/LICENSE.txt for license information. 573471bf0Spatrick // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception 673471bf0Spatrick // 773471bf0Spatrick //===----------------------------------------------------------------------===// 873471bf0Spatrick /// \file 973471bf0Spatrick /// 1073471bf0Spatrick /// This file provides the interface for the instcombine pass implementation. 1173471bf0Spatrick /// The interface is used for generic transformations in this folder and 1273471bf0Spatrick /// target specific combinations in the targets. 1373471bf0Spatrick /// The visitor implementation is in \c InstCombinerImpl in 1473471bf0Spatrick /// \c InstCombineInternal.h. 1573471bf0Spatrick /// 1673471bf0Spatrick //===----------------------------------------------------------------------===// 1773471bf0Spatrick 1873471bf0Spatrick #ifndef LLVM_TRANSFORMS_INSTCOMBINE_INSTCOMBINER_H 1973471bf0Spatrick #define LLVM_TRANSFORMS_INSTCOMBINE_INSTCOMBINER_H 2073471bf0Spatrick 2173471bf0Spatrick #include "llvm/Analysis/InstructionSimplify.h" 2273471bf0Spatrick #include "llvm/Analysis/TargetFolder.h" 2373471bf0Spatrick #include "llvm/Analysis/ValueTracking.h" 2473471bf0Spatrick #include "llvm/IR/IRBuilder.h" 2573471bf0Spatrick #include "llvm/IR/PatternMatch.h" 2673471bf0Spatrick #include "llvm/Support/Debug.h" 2773471bf0Spatrick #include "llvm/Support/KnownBits.h" 2873471bf0Spatrick #include <cassert> 2973471bf0Spatrick 3073471bf0Spatrick #define DEBUG_TYPE "instcombine" 31*d415bd75Srobert #include "llvm/Transforms/Utils/InstructionWorklist.h" 3273471bf0Spatrick 3373471bf0Spatrick namespace llvm { 3473471bf0Spatrick 3573471bf0Spatrick class AAResults; 3673471bf0Spatrick class AssumptionCache; 3773471bf0Spatrick class ProfileSummaryInfo; 3873471bf0Spatrick class TargetLibraryInfo; 3973471bf0Spatrick class TargetTransformInfo; 4073471bf0Spatrick 4173471bf0Spatrick /// The core instruction combiner logic. 4273471bf0Spatrick /// 4373471bf0Spatrick /// This class provides both the logic to recursively visit instructions and 4473471bf0Spatrick /// combine them. 4573471bf0Spatrick class LLVM_LIBRARY_VISIBILITY InstCombiner { 46*d415bd75Srobert /// Only used to call target specific intrinsic combining. 47*d415bd75Srobert /// It must **NOT** be used for any other purpose, as InstCombine is a 48*d415bd75Srobert /// target-independent canonicalization transform. 4973471bf0Spatrick TargetTransformInfo &TTI; 5073471bf0Spatrick 5173471bf0Spatrick public: 5273471bf0Spatrick /// Maximum size of array considered when transforming. 5373471bf0Spatrick uint64_t MaxArraySizeForCombine = 0; 5473471bf0Spatrick 5573471bf0Spatrick /// An IRBuilder that automatically inserts new instructions into the 5673471bf0Spatrick /// worklist. 5773471bf0Spatrick using BuilderTy = IRBuilder<TargetFolder, IRBuilderCallbackInserter>; 5873471bf0Spatrick BuilderTy &Builder; 5973471bf0Spatrick 6073471bf0Spatrick protected: 6173471bf0Spatrick /// A worklist of the instructions that need to be simplified. 62*d415bd75Srobert InstructionWorklist &Worklist; 6373471bf0Spatrick 6473471bf0Spatrick // Mode in which we are running the combiner. 6573471bf0Spatrick const bool MinimizeSize; 6673471bf0Spatrick 6773471bf0Spatrick AAResults *AA; 6873471bf0Spatrick 6973471bf0Spatrick // Required analyses. 7073471bf0Spatrick AssumptionCache &AC; 7173471bf0Spatrick TargetLibraryInfo &TLI; 7273471bf0Spatrick DominatorTree &DT; 7373471bf0Spatrick const DataLayout &DL; 7473471bf0Spatrick const SimplifyQuery SQ; 7573471bf0Spatrick OptimizationRemarkEmitter &ORE; 7673471bf0Spatrick BlockFrequencyInfo *BFI; 7773471bf0Spatrick ProfileSummaryInfo *PSI; 7873471bf0Spatrick 7973471bf0Spatrick // Optional analyses. When non-null, these can both be used to do better 8073471bf0Spatrick // combining and will be updated to reflect any changes. 8173471bf0Spatrick LoopInfo *LI; 8273471bf0Spatrick 8373471bf0Spatrick bool MadeIRChange = false; 8473471bf0Spatrick 8573471bf0Spatrick public: InstCombiner(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)86*d415bd75Srobert InstCombiner(InstructionWorklist &Worklist, BuilderTy &Builder, 8773471bf0Spatrick bool MinimizeSize, AAResults *AA, AssumptionCache &AC, 8873471bf0Spatrick TargetLibraryInfo &TLI, TargetTransformInfo &TTI, 8973471bf0Spatrick DominatorTree &DT, OptimizationRemarkEmitter &ORE, 9073471bf0Spatrick BlockFrequencyInfo *BFI, ProfileSummaryInfo *PSI, 9173471bf0Spatrick const DataLayout &DL, LoopInfo *LI) 9273471bf0Spatrick : TTI(TTI), Builder(Builder), Worklist(Worklist), 9373471bf0Spatrick MinimizeSize(MinimizeSize), AA(AA), AC(AC), TLI(TLI), DT(DT), DL(DL), 9473471bf0Spatrick SQ(DL, &TLI, &DT, &AC), ORE(ORE), BFI(BFI), PSI(PSI), LI(LI) {} 9573471bf0Spatrick 96*d415bd75Srobert virtual ~InstCombiner() = default; 9773471bf0Spatrick 9873471bf0Spatrick /// Return the source operand of a potentially bitcasted value while 9973471bf0Spatrick /// optionally checking if it has one use. If there is no bitcast or the one 10073471bf0Spatrick /// use check is not met, return the input value itself. 10173471bf0Spatrick static Value *peekThroughBitcast(Value *V, bool OneUseOnly = false) { 10273471bf0Spatrick if (auto *BitCast = dyn_cast<BitCastInst>(V)) 10373471bf0Spatrick if (!OneUseOnly || BitCast->hasOneUse()) 10473471bf0Spatrick return BitCast->getOperand(0); 10573471bf0Spatrick 10673471bf0Spatrick // V is not a bitcast or V has more than one use and OneUseOnly is true. 10773471bf0Spatrick return V; 10873471bf0Spatrick } 10973471bf0Spatrick 11073471bf0Spatrick /// Assign a complexity or rank value to LLVM Values. This is used to reduce 11173471bf0Spatrick /// the amount of pattern matching needed for compares and commutative 11273471bf0Spatrick /// instructions. For example, if we have: 11373471bf0Spatrick /// icmp ugt X, Constant 11473471bf0Spatrick /// or 11573471bf0Spatrick /// xor (add X, Constant), cast Z 11673471bf0Spatrick /// 11773471bf0Spatrick /// We do not have to consider the commuted variants of these patterns because 11873471bf0Spatrick /// canonicalization based on complexity guarantees the above ordering. 11973471bf0Spatrick /// 12073471bf0Spatrick /// This routine maps IR values to various complexity ranks: 12173471bf0Spatrick /// 0 -> undef 12273471bf0Spatrick /// 1 -> Constants 12373471bf0Spatrick /// 2 -> Other non-instructions 12473471bf0Spatrick /// 3 -> Arguments 12573471bf0Spatrick /// 4 -> Cast and (f)neg/not instructions 12673471bf0Spatrick /// 5 -> Other instructions getComplexity(Value * V)12773471bf0Spatrick static unsigned getComplexity(Value *V) { 12873471bf0Spatrick if (isa<Instruction>(V)) { 12973471bf0Spatrick if (isa<CastInst>(V) || match(V, m_Neg(PatternMatch::m_Value())) || 13073471bf0Spatrick match(V, m_Not(PatternMatch::m_Value())) || 13173471bf0Spatrick match(V, m_FNeg(PatternMatch::m_Value()))) 13273471bf0Spatrick return 4; 13373471bf0Spatrick return 5; 13473471bf0Spatrick } 13573471bf0Spatrick if (isa<Argument>(V)) 13673471bf0Spatrick return 3; 13773471bf0Spatrick return isa<Constant>(V) ? (isa<UndefValue>(V) ? 0 : 1) : 2; 13873471bf0Spatrick } 13973471bf0Spatrick 14073471bf0Spatrick /// Predicate canonicalization reduces the number of patterns that need to be 14173471bf0Spatrick /// matched by other transforms. For example, we may swap the operands of a 14273471bf0Spatrick /// conditional branch or select to create a compare with a canonical 14373471bf0Spatrick /// (inverted) predicate which is then more likely to be matched with other 14473471bf0Spatrick /// values. isCanonicalPredicate(CmpInst::Predicate Pred)14573471bf0Spatrick static bool isCanonicalPredicate(CmpInst::Predicate Pred) { 14673471bf0Spatrick switch (Pred) { 14773471bf0Spatrick case CmpInst::ICMP_NE: 14873471bf0Spatrick case CmpInst::ICMP_ULE: 14973471bf0Spatrick case CmpInst::ICMP_SLE: 15073471bf0Spatrick case CmpInst::ICMP_UGE: 15173471bf0Spatrick case CmpInst::ICMP_SGE: 15273471bf0Spatrick // TODO: There are 16 FCMP predicates. Should others be (not) canonical? 15373471bf0Spatrick case CmpInst::FCMP_ONE: 15473471bf0Spatrick case CmpInst::FCMP_OLE: 15573471bf0Spatrick case CmpInst::FCMP_OGE: 15673471bf0Spatrick return false; 15773471bf0Spatrick default: 15873471bf0Spatrick return true; 15973471bf0Spatrick } 16073471bf0Spatrick } 16173471bf0Spatrick 16273471bf0Spatrick /// Given an exploded icmp instruction, return true if the comparison only 16373471bf0Spatrick /// checks the sign bit. If it only checks the sign bit, set TrueIfSigned if 16473471bf0Spatrick /// the result of the comparison is true when the input value is signed. isSignBitCheck(ICmpInst::Predicate Pred,const APInt & RHS,bool & TrueIfSigned)16573471bf0Spatrick static bool isSignBitCheck(ICmpInst::Predicate Pred, const APInt &RHS, 16673471bf0Spatrick bool &TrueIfSigned) { 16773471bf0Spatrick switch (Pred) { 16873471bf0Spatrick case ICmpInst::ICMP_SLT: // True if LHS s< 0 16973471bf0Spatrick TrueIfSigned = true; 170*d415bd75Srobert return RHS.isZero(); 17173471bf0Spatrick case ICmpInst::ICMP_SLE: // True if LHS s<= -1 17273471bf0Spatrick TrueIfSigned = true; 173*d415bd75Srobert return RHS.isAllOnes(); 17473471bf0Spatrick case ICmpInst::ICMP_SGT: // True if LHS s> -1 17573471bf0Spatrick TrueIfSigned = false; 176*d415bd75Srobert return RHS.isAllOnes(); 17773471bf0Spatrick case ICmpInst::ICMP_SGE: // True if LHS s>= 0 17873471bf0Spatrick TrueIfSigned = false; 179*d415bd75Srobert return RHS.isZero(); 18073471bf0Spatrick case ICmpInst::ICMP_UGT: 18173471bf0Spatrick // True if LHS u> RHS and RHS == sign-bit-mask - 1 18273471bf0Spatrick TrueIfSigned = true; 18373471bf0Spatrick return RHS.isMaxSignedValue(); 18473471bf0Spatrick case ICmpInst::ICMP_UGE: 18573471bf0Spatrick // True if LHS u>= RHS and RHS == sign-bit-mask (2^7, 2^15, 2^31, etc) 18673471bf0Spatrick TrueIfSigned = true; 18773471bf0Spatrick return RHS.isMinSignedValue(); 18873471bf0Spatrick case ICmpInst::ICMP_ULT: 18973471bf0Spatrick // True if LHS u< RHS and RHS == sign-bit-mask (2^7, 2^15, 2^31, etc) 19073471bf0Spatrick TrueIfSigned = false; 19173471bf0Spatrick return RHS.isMinSignedValue(); 19273471bf0Spatrick case ICmpInst::ICMP_ULE: 19373471bf0Spatrick // True if LHS u<= RHS and RHS == sign-bit-mask - 1 19473471bf0Spatrick TrueIfSigned = false; 19573471bf0Spatrick return RHS.isMaxSignedValue(); 19673471bf0Spatrick default: 19773471bf0Spatrick return false; 19873471bf0Spatrick } 19973471bf0Spatrick } 20073471bf0Spatrick 20173471bf0Spatrick /// Add one to a Constant AddOne(Constant * C)20273471bf0Spatrick static Constant *AddOne(Constant *C) { 20373471bf0Spatrick return ConstantExpr::getAdd(C, ConstantInt::get(C->getType(), 1)); 20473471bf0Spatrick } 20573471bf0Spatrick 20673471bf0Spatrick /// Subtract one from a Constant SubOne(Constant * C)20773471bf0Spatrick static Constant *SubOne(Constant *C) { 20873471bf0Spatrick return ConstantExpr::getSub(C, ConstantInt::get(C->getType(), 1)); 20973471bf0Spatrick } 21073471bf0Spatrick 211*d415bd75Srobert std::optional<std::pair< 21273471bf0Spatrick CmpInst::Predicate, 21373471bf0Spatrick Constant *>> static getFlippedStrictnessPredicateAndConstant(CmpInst:: 21473471bf0Spatrick Predicate 21573471bf0Spatrick Pred, 21673471bf0Spatrick Constant *C); 21773471bf0Spatrick shouldAvoidAbsorbingNotIntoSelect(const SelectInst & SI)21873471bf0Spatrick static bool shouldAvoidAbsorbingNotIntoSelect(const SelectInst &SI) { 21973471bf0Spatrick // a ? b : false and a ? true : b are the canonical form of logical and/or. 22073471bf0Spatrick // This includes !a ? b : false and !a ? true : b. Absorbing the not into 22173471bf0Spatrick // the select by swapping operands would break recognition of this pattern 22273471bf0Spatrick // in other analyses, so don't do that. 22373471bf0Spatrick return match(&SI, PatternMatch::m_LogicalAnd(PatternMatch::m_Value(), 22473471bf0Spatrick PatternMatch::m_Value())) || 22573471bf0Spatrick match(&SI, PatternMatch::m_LogicalOr(PatternMatch::m_Value(), 22673471bf0Spatrick PatternMatch::m_Value())); 22773471bf0Spatrick } 22873471bf0Spatrick 22973471bf0Spatrick /// Return true if the specified value is free to invert (apply ~ to). 23073471bf0Spatrick /// This happens in cases where the ~ can be eliminated. If WillInvertAllUses 23173471bf0Spatrick /// is true, work under the assumption that the caller intends to remove all 23273471bf0Spatrick /// uses of V and only keep uses of ~V. 23373471bf0Spatrick /// 23473471bf0Spatrick /// See also: canFreelyInvertAllUsersOf() isFreeToInvert(Value * V,bool WillInvertAllUses)23573471bf0Spatrick static bool isFreeToInvert(Value *V, bool WillInvertAllUses) { 23673471bf0Spatrick // ~(~(X)) -> X. 23773471bf0Spatrick if (match(V, m_Not(PatternMatch::m_Value()))) 23873471bf0Spatrick return true; 23973471bf0Spatrick 24073471bf0Spatrick // Constants can be considered to be not'ed values. 24173471bf0Spatrick if (match(V, PatternMatch::m_AnyIntegralConstant())) 24273471bf0Spatrick return true; 24373471bf0Spatrick 24473471bf0Spatrick // Compares can be inverted if all of their uses are being modified to use 24573471bf0Spatrick // the ~V. 24673471bf0Spatrick if (isa<CmpInst>(V)) 24773471bf0Spatrick return WillInvertAllUses; 24873471bf0Spatrick 24973471bf0Spatrick // If `V` is of the form `A + Constant` then `-1 - V` can be folded into 25073471bf0Spatrick // `(-1 - Constant) - A` if we are willing to invert all of the uses. 251*d415bd75Srobert if (match(V, m_Add(PatternMatch::m_Value(), PatternMatch::m_ImmConstant()))) 252*d415bd75Srobert return WillInvertAllUses; 253*d415bd75Srobert 254*d415bd75Srobert // If `V` is of the form `Constant - A` then `-1 - V` can be folded into 255*d415bd75Srobert // `A + (-1 - Constant)` if we are willing to invert all of the uses. 256*d415bd75Srobert if (match(V, m_Sub(PatternMatch::m_ImmConstant(), PatternMatch::m_Value()))) 25773471bf0Spatrick return WillInvertAllUses; 25873471bf0Spatrick 25973471bf0Spatrick // Selects with invertible operands are freely invertible 26073471bf0Spatrick if (match(V, 26173471bf0Spatrick m_Select(PatternMatch::m_Value(), m_Not(PatternMatch::m_Value()), 26273471bf0Spatrick m_Not(PatternMatch::m_Value())))) 26373471bf0Spatrick return WillInvertAllUses; 26473471bf0Spatrick 265*d415bd75Srobert // Min/max may be in the form of intrinsics, so handle those identically 266*d415bd75Srobert // to select patterns. 267*d415bd75Srobert if (match(V, m_MaxOrMin(m_Not(PatternMatch::m_Value()), 268*d415bd75Srobert m_Not(PatternMatch::m_Value())))) 269*d415bd75Srobert return WillInvertAllUses; 270*d415bd75Srobert 27173471bf0Spatrick return false; 27273471bf0Spatrick } 27373471bf0Spatrick 27473471bf0Spatrick /// Given i1 V, can every user of V be freely adapted if V is changed to !V ? 27573471bf0Spatrick /// InstCombine's freelyInvertAllUsersOf() must be kept in sync with this fn. 276*d415bd75Srobert /// NOTE: for Instructions only! 27773471bf0Spatrick /// 27873471bf0Spatrick /// See also: isFreeToInvert() canFreelyInvertAllUsersOf(Instruction * V,Value * IgnoredUser)279*d415bd75Srobert static bool canFreelyInvertAllUsersOf(Instruction *V, Value *IgnoredUser) { 28073471bf0Spatrick // Look at every user of V. 28173471bf0Spatrick for (Use &U : V->uses()) { 28273471bf0Spatrick if (U.getUser() == IgnoredUser) 28373471bf0Spatrick continue; // Don't consider this user. 28473471bf0Spatrick 28573471bf0Spatrick auto *I = cast<Instruction>(U.getUser()); 28673471bf0Spatrick switch (I->getOpcode()) { 28773471bf0Spatrick case Instruction::Select: 28873471bf0Spatrick if (U.getOperandNo() != 0) // Only if the value is used as select cond. 28973471bf0Spatrick return false; 29073471bf0Spatrick if (shouldAvoidAbsorbingNotIntoSelect(*cast<SelectInst>(I))) 29173471bf0Spatrick return false; 29273471bf0Spatrick break; 29373471bf0Spatrick case Instruction::Br: 29473471bf0Spatrick assert(U.getOperandNo() == 0 && "Must be branching on that value."); 29573471bf0Spatrick break; // Free to invert by swapping true/false values/destinations. 29673471bf0Spatrick case Instruction::Xor: // Can invert 'xor' if it's a 'not', by ignoring 29773471bf0Spatrick // it. 29873471bf0Spatrick if (!match(I, m_Not(PatternMatch::m_Value()))) 29973471bf0Spatrick return false; // Not a 'not'. 30073471bf0Spatrick break; 30173471bf0Spatrick default: 30273471bf0Spatrick return false; // Don't know, likely not freely invertible. 30373471bf0Spatrick } 30473471bf0Spatrick // So far all users were free to invert... 30573471bf0Spatrick } 30673471bf0Spatrick return true; // Can freely invert all users! 30773471bf0Spatrick } 30873471bf0Spatrick 30973471bf0Spatrick /// Some binary operators require special handling to avoid poison and 31073471bf0Spatrick /// undefined behavior. If a constant vector has undef elements, replace those 31173471bf0Spatrick /// undefs with identity constants if possible because those are always safe 31273471bf0Spatrick /// to execute. If no identity constant exists, replace undef with some other 31373471bf0Spatrick /// safe constant. 31473471bf0Spatrick static Constant * getSafeVectorConstantForBinop(BinaryOperator::BinaryOps Opcode,Constant * In,bool IsRHSConstant)31573471bf0Spatrick getSafeVectorConstantForBinop(BinaryOperator::BinaryOps Opcode, Constant *In, 31673471bf0Spatrick bool IsRHSConstant) { 31773471bf0Spatrick auto *InVTy = cast<FixedVectorType>(In->getType()); 31873471bf0Spatrick 31973471bf0Spatrick Type *EltTy = InVTy->getElementType(); 32073471bf0Spatrick auto *SafeC = ConstantExpr::getBinOpIdentity(Opcode, EltTy, IsRHSConstant); 32173471bf0Spatrick if (!SafeC) { 32273471bf0Spatrick // TODO: Should this be available as a constant utility function? It is 32373471bf0Spatrick // similar to getBinOpAbsorber(). 32473471bf0Spatrick if (IsRHSConstant) { 32573471bf0Spatrick switch (Opcode) { 32673471bf0Spatrick case Instruction::SRem: // X % 1 = 0 32773471bf0Spatrick case Instruction::URem: // X %u 1 = 0 32873471bf0Spatrick SafeC = ConstantInt::get(EltTy, 1); 32973471bf0Spatrick break; 33073471bf0Spatrick case Instruction::FRem: // X % 1.0 (doesn't simplify, but it is safe) 33173471bf0Spatrick SafeC = ConstantFP::get(EltTy, 1.0); 33273471bf0Spatrick break; 33373471bf0Spatrick default: 33473471bf0Spatrick llvm_unreachable( 33573471bf0Spatrick "Only rem opcodes have no identity constant for RHS"); 33673471bf0Spatrick } 33773471bf0Spatrick } else { 33873471bf0Spatrick switch (Opcode) { 33973471bf0Spatrick case Instruction::Shl: // 0 << X = 0 34073471bf0Spatrick case Instruction::LShr: // 0 >>u X = 0 34173471bf0Spatrick case Instruction::AShr: // 0 >> X = 0 34273471bf0Spatrick case Instruction::SDiv: // 0 / X = 0 34373471bf0Spatrick case Instruction::UDiv: // 0 /u X = 0 34473471bf0Spatrick case Instruction::SRem: // 0 % X = 0 34573471bf0Spatrick case Instruction::URem: // 0 %u X = 0 34673471bf0Spatrick case Instruction::Sub: // 0 - X (doesn't simplify, but it is safe) 34773471bf0Spatrick case Instruction::FSub: // 0.0 - X (doesn't simplify, but it is safe) 34873471bf0Spatrick case Instruction::FDiv: // 0.0 / X (doesn't simplify, but it is safe) 34973471bf0Spatrick case Instruction::FRem: // 0.0 % X = 0 35073471bf0Spatrick SafeC = Constant::getNullValue(EltTy); 35173471bf0Spatrick break; 35273471bf0Spatrick default: 35373471bf0Spatrick llvm_unreachable("Expected to find identity constant for opcode"); 35473471bf0Spatrick } 35573471bf0Spatrick } 35673471bf0Spatrick } 35773471bf0Spatrick assert(SafeC && "Must have safe constant for binop"); 35873471bf0Spatrick unsigned NumElts = InVTy->getNumElements(); 35973471bf0Spatrick SmallVector<Constant *, 16> Out(NumElts); 36073471bf0Spatrick for (unsigned i = 0; i != NumElts; ++i) { 36173471bf0Spatrick Constant *C = In->getAggregateElement(i); 36273471bf0Spatrick Out[i] = isa<UndefValue>(C) ? SafeC : C; 36373471bf0Spatrick } 36473471bf0Spatrick return ConstantVector::get(Out); 36573471bf0Spatrick } 36673471bf0Spatrick addToWorklist(Instruction * I)36773471bf0Spatrick void addToWorklist(Instruction *I) { Worklist.push(I); } 36873471bf0Spatrick getAssumptionCache()36973471bf0Spatrick AssumptionCache &getAssumptionCache() const { return AC; } getTargetLibraryInfo()37073471bf0Spatrick TargetLibraryInfo &getTargetLibraryInfo() const { return TLI; } getDominatorTree()37173471bf0Spatrick DominatorTree &getDominatorTree() const { return DT; } getDataLayout()37273471bf0Spatrick const DataLayout &getDataLayout() const { return DL; } getSimplifyQuery()37373471bf0Spatrick const SimplifyQuery &getSimplifyQuery() const { return SQ; } getOptimizationRemarkEmitter()37473471bf0Spatrick OptimizationRemarkEmitter &getOptimizationRemarkEmitter() const { 37573471bf0Spatrick return ORE; 37673471bf0Spatrick } getBlockFrequencyInfo()37773471bf0Spatrick BlockFrequencyInfo *getBlockFrequencyInfo() const { return BFI; } getProfileSummaryInfo()37873471bf0Spatrick ProfileSummaryInfo *getProfileSummaryInfo() const { return PSI; } getLoopInfo()37973471bf0Spatrick LoopInfo *getLoopInfo() const { return LI; } 38073471bf0Spatrick 38173471bf0Spatrick // Call target specific combiners 382*d415bd75Srobert std::optional<Instruction *> targetInstCombineIntrinsic(IntrinsicInst &II); 383*d415bd75Srobert std::optional<Value *> 38473471bf0Spatrick targetSimplifyDemandedUseBitsIntrinsic(IntrinsicInst &II, APInt DemandedMask, 38573471bf0Spatrick KnownBits &Known, 38673471bf0Spatrick bool &KnownBitsComputed); 387*d415bd75Srobert std::optional<Value *> targetSimplifyDemandedVectorEltsIntrinsic( 38873471bf0Spatrick IntrinsicInst &II, APInt DemandedElts, APInt &UndefElts, 38973471bf0Spatrick APInt &UndefElts2, APInt &UndefElts3, 39073471bf0Spatrick std::function<void(Instruction *, unsigned, APInt, APInt &)> 39173471bf0Spatrick SimplifyAndSetOp); 39273471bf0Spatrick 39373471bf0Spatrick /// Inserts an instruction \p New before instruction \p Old 39473471bf0Spatrick /// 39573471bf0Spatrick /// Also adds the new instruction to the worklist and returns \p New so that 39673471bf0Spatrick /// it is suitable for use as the return from the visitation patterns. InsertNewInstBefore(Instruction * New,Instruction & Old)39773471bf0Spatrick Instruction *InsertNewInstBefore(Instruction *New, Instruction &Old) { 39873471bf0Spatrick assert(New && !New->getParent() && 39973471bf0Spatrick "New instruction already inserted into a basic block!"); 40073471bf0Spatrick BasicBlock *BB = Old.getParent(); 401*d415bd75Srobert New->insertInto(BB, Old.getIterator()); // Insert inst 402*d415bd75Srobert Worklist.add(New); 40373471bf0Spatrick return New; 40473471bf0Spatrick } 40573471bf0Spatrick 40673471bf0Spatrick /// Same as InsertNewInstBefore, but also sets the debug loc. InsertNewInstWith(Instruction * New,Instruction & Old)40773471bf0Spatrick Instruction *InsertNewInstWith(Instruction *New, Instruction &Old) { 40873471bf0Spatrick New->setDebugLoc(Old.getDebugLoc()); 40973471bf0Spatrick return InsertNewInstBefore(New, Old); 41073471bf0Spatrick } 41173471bf0Spatrick 41273471bf0Spatrick /// A combiner-aware RAUW-like routine. 41373471bf0Spatrick /// 41473471bf0Spatrick /// This method is to be used when an instruction is found to be dead, 41573471bf0Spatrick /// replaceable with another preexisting expression. Here we add all uses of 41673471bf0Spatrick /// I to the worklist, replace all uses of I with the new value, then return 41773471bf0Spatrick /// I, so that the inst combiner will know that I was modified. replaceInstUsesWith(Instruction & I,Value * V)41873471bf0Spatrick Instruction *replaceInstUsesWith(Instruction &I, Value *V) { 41973471bf0Spatrick // If there are no uses to replace, then we return nullptr to indicate that 42073471bf0Spatrick // no changes were made to the program. 421*d415bd75Srobert if (I.use_empty()) return nullptr; 42273471bf0Spatrick 42373471bf0Spatrick Worklist.pushUsersToWorkList(I); // Add all modified instrs to worklist. 42473471bf0Spatrick 42573471bf0Spatrick // If we are replacing the instruction with itself, this must be in a 42673471bf0Spatrick // segment of unreachable code, so just clobber the instruction. 42773471bf0Spatrick if (&I == V) 428*d415bd75Srobert V = PoisonValue::get(I.getType()); 42973471bf0Spatrick 43073471bf0Spatrick LLVM_DEBUG(dbgs() << "IC: Replacing " << I << "\n" 43173471bf0Spatrick << " with " << *V << '\n'); 43273471bf0Spatrick 433*d415bd75Srobert // If V is a new unnamed instruction, take the name from the old one. 434*d415bd75Srobert if (V->use_empty() && isa<Instruction>(V) && !V->hasName() && I.hasName()) 435*d415bd75Srobert V->takeName(&I); 436*d415bd75Srobert 43773471bf0Spatrick I.replaceAllUsesWith(V); 43873471bf0Spatrick return &I; 43973471bf0Spatrick } 44073471bf0Spatrick 44173471bf0Spatrick /// Replace operand of instruction and add old operand to the worklist. replaceOperand(Instruction & I,unsigned OpNum,Value * V)44273471bf0Spatrick Instruction *replaceOperand(Instruction &I, unsigned OpNum, Value *V) { 44373471bf0Spatrick Worklist.addValue(I.getOperand(OpNum)); 44473471bf0Spatrick I.setOperand(OpNum, V); 44573471bf0Spatrick return &I; 44673471bf0Spatrick } 44773471bf0Spatrick 44873471bf0Spatrick /// Replace use and add the previously used value to the worklist. replaceUse(Use & U,Value * NewValue)44973471bf0Spatrick void replaceUse(Use &U, Value *NewValue) { 45073471bf0Spatrick Worklist.addValue(U); 45173471bf0Spatrick U = NewValue; 45273471bf0Spatrick } 45373471bf0Spatrick 45473471bf0Spatrick /// Combiner aware instruction erasure. 45573471bf0Spatrick /// 45673471bf0Spatrick /// When dealing with an instruction that has side effects or produces a void 45773471bf0Spatrick /// value, we can't rely on DCE to delete the instruction. Instead, visit 45873471bf0Spatrick /// methods should return the value returned by this function. 45973471bf0Spatrick virtual Instruction *eraseInstFromFunction(Instruction &I) = 0; 46073471bf0Spatrick computeKnownBits(const Value * V,KnownBits & Known,unsigned Depth,const Instruction * CxtI)46173471bf0Spatrick void computeKnownBits(const Value *V, KnownBits &Known, unsigned Depth, 46273471bf0Spatrick const Instruction *CxtI) const { 46373471bf0Spatrick llvm::computeKnownBits(V, Known, DL, Depth, &AC, CxtI, &DT); 46473471bf0Spatrick } 46573471bf0Spatrick computeKnownBits(const Value * V,unsigned Depth,const Instruction * CxtI)46673471bf0Spatrick KnownBits computeKnownBits(const Value *V, unsigned Depth, 46773471bf0Spatrick const Instruction *CxtI) const { 46873471bf0Spatrick return llvm::computeKnownBits(V, DL, Depth, &AC, CxtI, &DT); 46973471bf0Spatrick } 47073471bf0Spatrick 47173471bf0Spatrick bool isKnownToBeAPowerOfTwo(const Value *V, bool OrZero = false, 47273471bf0Spatrick unsigned Depth = 0, 47373471bf0Spatrick const Instruction *CxtI = nullptr) { 47473471bf0Spatrick return llvm::isKnownToBeAPowerOfTwo(V, DL, OrZero, Depth, &AC, CxtI, &DT); 47573471bf0Spatrick } 47673471bf0Spatrick 47773471bf0Spatrick bool MaskedValueIsZero(const Value *V, const APInt &Mask, unsigned Depth = 0, 47873471bf0Spatrick const Instruction *CxtI = nullptr) const { 47973471bf0Spatrick return llvm::MaskedValueIsZero(V, Mask, DL, Depth, &AC, CxtI, &DT); 48073471bf0Spatrick } 48173471bf0Spatrick 48273471bf0Spatrick unsigned ComputeNumSignBits(const Value *Op, unsigned Depth = 0, 48373471bf0Spatrick const Instruction *CxtI = nullptr) const { 48473471bf0Spatrick return llvm::ComputeNumSignBits(Op, DL, Depth, &AC, CxtI, &DT); 48573471bf0Spatrick } 48673471bf0Spatrick 487*d415bd75Srobert unsigned ComputeMaxSignificantBits(const Value *Op, unsigned Depth = 0, 488*d415bd75Srobert const Instruction *CxtI = nullptr) const { 489*d415bd75Srobert return llvm::ComputeMaxSignificantBits(Op, DL, Depth, &AC, CxtI, &DT); 490*d415bd75Srobert } 491*d415bd75Srobert computeOverflowForUnsignedMul(const Value * LHS,const Value * RHS,const Instruction * CxtI)49273471bf0Spatrick OverflowResult computeOverflowForUnsignedMul(const Value *LHS, 49373471bf0Spatrick const Value *RHS, 49473471bf0Spatrick const Instruction *CxtI) const { 49573471bf0Spatrick return llvm::computeOverflowForUnsignedMul(LHS, RHS, DL, &AC, CxtI, &DT); 49673471bf0Spatrick } 49773471bf0Spatrick computeOverflowForSignedMul(const Value * LHS,const Value * RHS,const Instruction * CxtI)49873471bf0Spatrick OverflowResult computeOverflowForSignedMul(const Value *LHS, const Value *RHS, 49973471bf0Spatrick const Instruction *CxtI) const { 50073471bf0Spatrick return llvm::computeOverflowForSignedMul(LHS, RHS, DL, &AC, CxtI, &DT); 50173471bf0Spatrick } 50273471bf0Spatrick computeOverflowForUnsignedAdd(const Value * LHS,const Value * RHS,const Instruction * CxtI)50373471bf0Spatrick OverflowResult computeOverflowForUnsignedAdd(const Value *LHS, 50473471bf0Spatrick const Value *RHS, 50573471bf0Spatrick const Instruction *CxtI) const { 50673471bf0Spatrick return llvm::computeOverflowForUnsignedAdd(LHS, RHS, DL, &AC, CxtI, &DT); 50773471bf0Spatrick } 50873471bf0Spatrick computeOverflowForSignedAdd(const Value * LHS,const Value * RHS,const Instruction * CxtI)50973471bf0Spatrick OverflowResult computeOverflowForSignedAdd(const Value *LHS, const Value *RHS, 51073471bf0Spatrick const Instruction *CxtI) const { 51173471bf0Spatrick return llvm::computeOverflowForSignedAdd(LHS, RHS, DL, &AC, CxtI, &DT); 51273471bf0Spatrick } 51373471bf0Spatrick computeOverflowForUnsignedSub(const Value * LHS,const Value * RHS,const Instruction * CxtI)51473471bf0Spatrick OverflowResult computeOverflowForUnsignedSub(const Value *LHS, 51573471bf0Spatrick const Value *RHS, 51673471bf0Spatrick const Instruction *CxtI) const { 51773471bf0Spatrick return llvm::computeOverflowForUnsignedSub(LHS, RHS, DL, &AC, CxtI, &DT); 51873471bf0Spatrick } 51973471bf0Spatrick computeOverflowForSignedSub(const Value * LHS,const Value * RHS,const Instruction * CxtI)52073471bf0Spatrick OverflowResult computeOverflowForSignedSub(const Value *LHS, const Value *RHS, 52173471bf0Spatrick const Instruction *CxtI) const { 52273471bf0Spatrick return llvm::computeOverflowForSignedSub(LHS, RHS, DL, &AC, CxtI, &DT); 52373471bf0Spatrick } 52473471bf0Spatrick 52573471bf0Spatrick virtual bool SimplifyDemandedBits(Instruction *I, unsigned OpNo, 52673471bf0Spatrick const APInt &DemandedMask, KnownBits &Known, 52773471bf0Spatrick unsigned Depth = 0) = 0; 52873471bf0Spatrick virtual Value * 52973471bf0Spatrick SimplifyDemandedVectorElts(Value *V, APInt DemandedElts, APInt &UndefElts, 53073471bf0Spatrick unsigned Depth = 0, 53173471bf0Spatrick bool AllowMultipleUsers = false) = 0; 53273471bf0Spatrick }; 53373471bf0Spatrick 53473471bf0Spatrick } // namespace llvm 53573471bf0Spatrick 53673471bf0Spatrick #undef DEBUG_TYPE 53773471bf0Spatrick 53873471bf0Spatrick #endif 539