37using namespace PatternMatch;
39#define DEBUG_TYPE "aggressive-instcombine"
41STATISTIC(NumAnyOrAllBitsSet,
"Number of any/all-bits-set patterns folded");
43 "Number of guarded rotates transformed into funnel shifts");
45 "Number of guarded funnel shifts transformed into funnel shifts");
46STATISTIC(NumPopCountRecognized,
"Number of popcount idioms recognized");
50 cl::desc(
"Max number of instructions to scan for aggressive instcombine."));
54 cl::desc(
"The maximum length of a constant string for a builtin string cmp "
55 "call eligible for inlining. The default value is 3."));
59 cl::desc(
"The maximum length of a constant string to "
60 "inline a memchr call."));
66 if (
I.getOpcode() != Instruction::PHI ||
I.getNumOperands() != 2)
80 unsigned Width = V->getType()->getScalarSizeInBits();
88 return Intrinsic::fshl;
97 return Intrinsic::fshr;
109 unsigned FunnelOp = 0, GuardOp = 1;
110 Value *P0 = Phi.getOperand(0), *P1 = Phi.getOperand(1);
111 Value *ShVal0, *ShVal1, *ShAmt;
114 (IID == Intrinsic::fshl && ShVal0 != P1) ||
115 (IID == Intrinsic::fshr && ShVal1 != P1)) {
118 (IID == Intrinsic::fshl && ShVal0 != P0) ||
119 (IID == Intrinsic::fshr && ShVal1 != P0))
121 assert((IID == Intrinsic::fshl || IID == Intrinsic::fshr) &&
122 "Pattern must match funnel shift left or right");
130 BasicBlock *GuardBB = Phi.getIncomingBlock(GuardOp);
131 BasicBlock *FunnelBB = Phi.getIncomingBlock(FunnelOp);
149 if (ShVal0 == ShVal1)
152 ++NumGuardedFunnelShifts;
156 bool IsFshl = IID == Intrinsic::fshl;
157 if (ShVal0 != ShVal1) {
179 Phi.replaceAllUsesWith(Builder.
CreateCall(
F, {ShVal0, ShVal1, ShAmt}));
225 const APInt *BitIndex =
nullptr;
231 MOps.
Root = Candidate;
239 return MOps.
Root == Candidate;
253 bool MatchAllBitsSet;
255 MatchAllBitsSet =
true;
257 MatchAllBitsSet =
false;
261 MaskOps MOps(
I.getType()->getScalarSizeInBits(), MatchAllBitsSet);
262 if (MatchAllBitsSet) {
278 I.replaceAllUsesWith(Zext);
279 ++NumAnyOrAllBitsSet;
295 if (
I.getOpcode() != Instruction::LShr)
298 Type *Ty =
I.getType();
304 if (!(Len <= 128 && Len > 8 && Len % 8 == 0))
313 Value *Op0 =
I.getOperand(0);
314 Value *Op1 =
I.getOperand(1);
330 Value *Root, *SubOp1;
338 I.getModule(), Intrinsic::ctpop,
I.getType());
339 I.replaceAllUsesWith(Builder.
CreateCall(Func, {Root}));
340 ++NumPopCountRecognized;
361 const APInt *MinC, *MaxC;
371 if (!(*MinC + 1).isPowerOf2() || -*MaxC != *MinC + 1)
374 Type *IntTy =
I.getType();
375 Type *FpTy = In->getType();
378 if (
auto *VecTy = dyn_cast<VectorType>(IntTy))
379 SatTy = VectorType::get(SatTy, VecTy->getElementCount());
400 if (SatCost >= MinMaxCost)
407 I.replaceAllUsesWith(Builder.
CreateSExt(Sat, IntTy));
418 Module *M = Call->getModule();
426 Type *Ty = Call->getType();
427 Value *Arg = Call->getArgOperand(0);
429 (Call->hasNoNaNs() ||
432 SimplifyQuery(Call->getDataLayout(), &TLI, &DT, &AC, Call)))) {
439 Call->replaceAllUsesWith(NewSqrt);
443 Call->eraseFromParent();
456 if (Length < InputBits || Length > InputBits * 2)
460 unsigned Matched = 0;
462 for (
unsigned i = 0; i <
Length; i++) {
464 if (Element >= InputBits)
471 if ((((
Mul << Element) & Mask.getZExtValue()) >> Shift) == i)
475 return Matched == InputBits;
542 if (!
GEP || !
GEP->isInBounds() ||
GEP->getNumIndices() != 2)
545 if (!
GEP->getSourceElementType()->isArrayTy())
548 uint64_t ArraySize =
GEP->getSourceElementType()->getArrayNumElements();
549 if (ArraySize != 32 && ArraySize != 64)
564 Value *Idx2 = std::next(
GEP->idx_begin())->get();
576 if (InputBits != 32 && InputBits != 64)
580 if (InputBits -
Log2_32(InputBits) != ShiftConst &&
581 InputBits -
Log2_32(InputBits) - 1 != ShiftConst)
584 if (!
isCTTZTable(*ConstData, MulConst, ShiftConst, InputBits))
588 bool DefinedForZero = ZeroTableElem == InputBits;
593 auto Cttz =
B.CreateIntrinsic(Intrinsic::cttz, {XType}, {X1, BoolConst});
594 Value *ZExtOrTrunc =
nullptr;
596 if (DefinedForZero) {
597 ZExtOrTrunc =
B.CreateZExtOrTrunc(Cttz, AccessType);
601 auto Cmp =
B.CreateICmpEQ(X1, ConstantInt::get(XType, 0));
603 B.CreateSelect(Cmp, ConstantInt::get(XType, ZeroTableElem), Cttz);
608 ZExtOrTrunc =
B.CreateZExtOrTrunc(
Select, AccessType);
634 const APInt *ShAmt2 =
nullptr;
658 LI1 = dyn_cast<LoadInst>(L1);
660 LoadInst *LI2 = dyn_cast<LoadInst>(L2);
672 bool IsBigEndian =
DL.isBigEndian();
690 if (Load1Ptr != Load2Ptr || LoadSize1 != LoadSize2)
700 if (!Start->comesBefore(
End)) {
707 unsigned NumScanned = 0;
721 if (Offset2.
slt(Offset1)) {
752 uint64_t ShiftDiff = IsBigEndian ? LoadSize2 : LoadSize1;
755 if ((Shift2 - Shift1) != ShiftDiff || (Offset2 - Offset1) != PrevSize)
765 LOps.
LoadSize = LoadSize1 + LoadSize2;
784 if (isa<VectorType>(
I.getType()))
800 unsigned AS = LI1->getPointerAddressSpace();
803 AS, LI1->getAlign(), &
Fast);
804 if (!Allowed || !
Fast)
808 Value *Load1Ptr = LI1->getPointerOperand();
819 LI1->isVolatile(),
"");
825 Value *NewOp = NewLoad;
833 NewOp = Builder.
CreateShl(NewOp, ConstantInt::get(
I.getContext(), *LOps.
Shift));
834 I.replaceAllUsesWith(NewOp);
841static std::pair<APInt, APInt>
843 unsigned BW =
DL.getIndexTypeSizeInBits(PtrOp->
getType());
844 std::optional<APInt> Stride;
845 APInt ModOffset(BW, 0);
848 while (
auto *
GEP = dyn_cast<GEPOperator>(PtrOp)) {
850 if (!
GEP->collectOffset(
DL, BW, VarOffsets, ModOffset))
853 for (
auto [V, Scale] : VarOffsets) {
855 if (!
GEP->isInBounds())
864 PtrOp =
GEP->getPointerOperand();
869 if (!isa<GlobalVariable>(PtrOp) || !Stride)
874 ModOffset = ModOffset.
srem(*Stride);
876 ModOffset += *Stride;
878 return {*Stride, ModOffset};
884 auto *LI = dyn_cast<LoadInst>(&
I);
885 if (!LI || LI->isVolatile())
890 auto *PtrOp = LI->getPointerOperand();
892 if (!GV || !GV->isConstant() || !GV->hasDefinitiveInitializer())
897 uint64_t GVSize =
DL.getTypeAllocSize(
C->getType());
898 if (!GVSize || 4096 < GVSize)
901 Type *LoadTy = LI->getType();
902 unsigned BW =
DL.getIndexTypeSizeInBits(PtrOp->getType());
908 if (
auto LA = LI->getAlign();
909 LA <= GV->
getAlign().valueOrOne() && Stride.getZExtValue() < LA.value()) {
910 ConstOffset =
APInt(BW, 0);
911 Stride =
APInt(BW, LA.value());
918 unsigned E = GVSize -
DL.getTypeStoreSize(LoadTy);
919 for (; ConstOffset.getZExtValue() <= E; ConstOffset += Stride)
923 I.replaceAllUsesWith(Ca);
929class StrNCmpInliner {
935 bool optimizeStrNCmp();
976bool StrNCmpInliner::optimizeStrNCmp() {
983 Value *Str1P = CI->getArgOperand(0);
984 Value *Str2P = CI->getArgOperand(1);
992 if (HasStr1 == HasStr2)
997 Value *StrP = HasStr1 ? Str2P : Str1P;
999 size_t Idx = Str.find(
'\0');
1001 if (Func == LibFunc_strncmp) {
1002 if (
auto *ConstInt = dyn_cast<ConstantInt>(CI->getArgOperand(2)))
1003 N = std::min(
N, ConstInt->getZExtValue());
1013 bool CanBeNull =
false, CanBeFreed =
false;
1016 inlineCompare(StrP, Str,
N, HasStr1);
1056 auto &Ctx = CI->getContext();
1069 cast<BranchInst>(BBCI->
getTerminator())->setSuccessor(0, BBSubs[0]);
1071 B.SetInsertPoint(BBNE);
1077 B.SetInsertPoint(BBSubs[i]);
1079 B.CreateZExt(
B.CreateLoad(
B.getInt8Ty(),
1080 B.CreateInBoundsPtrAdd(
Base,
B.getInt64(i))),
1083 ConstantInt::get(CI->getType(),
static_cast<unsigned char>(RHS[i]));
1084 Value *Sub = Swapped ?
B.CreateSub(VR, VL) :
B.CreateSub(VL, VR);
1086 B.CreateCondBr(
B.CreateICmpNE(Sub, ConstantInt::get(CI->getType(), 0)),
1087 BBNE, BBSubs[i + 1]);
1091 Phi->addIncoming(Sub, BBSubs[i]);
1094 CI->replaceAllUsesWith(Phi);
1095 CI->eraseFromParent();
1099 Updates.
push_back({DominatorTree::Insert, BBCI, BBSubs[0]});
1102 Updates.
push_back({DominatorTree::Insert, BBSubs[i], BBSubs[i + 1]});
1103 Updates.
push_back({DominatorTree::Insert, BBSubs[i], BBNE});
1105 Updates.
push_back({DominatorTree::Insert, BBNE, BBTail});
1106 Updates.
push_back({DominatorTree::Delete, BBCI, BBTail});
1107 DTU->applyUpdates(Updates);
1114 if (isa<Constant>(Call->getArgOperand(1)))
1123 if (
auto *ConstInt = dyn_cast<ConstantInt>(Call->getArgOperand(2))) {
1124 uint64_t Val = ConstInt->getZExtValue();
1141 IRB.
CreateTrunc(Call->getArgOperand(1), ByteTy), BBNext,
N);
1142 Type *IndexTy =
DL.getIndexType(Call->getType());
1146 Call->getContext(),
"memchr.success", BB->
getParent(), BBNext);
1152 Updates.
push_back({DominatorTree::Insert, BBSuccess, BBNext});
1156 ConstantInt *CaseVal = ConstantInt::get(ByteTy, Str[
I]);
1157 if (!Cases.
insert(CaseVal).second)
1162 SI->addCase(CaseVal, BBCase);
1164 IndexPHI->
addIncoming(ConstantInt::get(IndexTy,
I), BBCase);
1167 Updates.
push_back({DominatorTree::Insert, BB, BBCase});
1168 Updates.
push_back({DominatorTree::Insert, BBCase, BBSuccess});
1175 PHI->addIncoming(FirstOccursLocation, BBSuccess);
1177 Call->replaceAllUsesWith(
PHI);
1178 Call->eraseFromParent();
1189 bool &MadeCFGChange) {
1191 auto *CI = dyn_cast<CallInst>(&
I);
1192 if (!CI || CI->isNoBuiltin())
1195 Function *CalledFunc = CI->getCalledFunction();
1211 case LibFunc_strcmp:
1212 case LibFunc_strncmp:
1213 if (StrNCmpInliner(CI, LF, &DTU,
DL).optimizeStrNCmp()) {
1214 MadeCFGChange =
true;
1218 case LibFunc_memchr:
1220 MadeCFGChange =
true;
1236 bool MadeChange =
false;
1277 bool MadeChange =
false;
1280 MadeChange |= TIC.
run(
F);
1292 bool MadeCFGChange =
false;
1293 if (!
runImpl(
F, AC,
TTI, TLI, DT, AA, MadeCFGChange)) {
amdgpu AMDGPU Register Bank Select
MachineBasicBlock MachineBasicBlock::iterator DebugLoc DL
static bool tryToRecognizePopCount(Instruction &I)
static bool foldSqrt(CallInst *Call, LibFunc Func, TargetTransformInfo &TTI, TargetLibraryInfo &TLI, AssumptionCache &AC, DominatorTree &DT)
Try to replace a mathlib call to sqrt with the LLVM intrinsic.
static bool foldAnyOrAllBitsSet(Instruction &I)
Match patterns that correspond to "any-bits-set" and "all-bits-set".
static cl::opt< unsigned > MemChrInlineThreshold("memchr-inline-threshold", cl::init(3), cl::Hidden, cl::desc("The maximum length of a constant string to " "inline a memchr call."))
static bool tryToFPToSat(Instruction &I, TargetTransformInfo &TTI)
Fold smin(smax(fptosi(x), C1), C2) to llvm.fptosi.sat(x), providing C1 and C2 saturate the value of t...
static cl::opt< unsigned > StrNCmpInlineThreshold("strncmp-inline-threshold", cl::init(3), cl::Hidden, cl::desc("The maximum length of a constant string for a builtin string cmp " "call eligible for inlining. The default value is 3."))
static bool matchAndOrChain(Value *V, MaskOps &MOps)
This is a recursive helper for foldAnyOrAllBitsSet() that walks through a chain of 'and' or 'or' inst...
static bool foldMemChr(CallInst *Call, DomTreeUpdater *DTU, const DataLayout &DL)
Convert memchr with a small constant string into a switch.
static bool foldConsecutiveLoads(Instruction &I, const DataLayout &DL, TargetTransformInfo &TTI, AliasAnalysis &AA, const DominatorTree &DT)
static bool runImpl(Function &F, AssumptionCache &AC, TargetTransformInfo &TTI, TargetLibraryInfo &TLI, DominatorTree &DT, AliasAnalysis &AA, bool &MadeCFGChange)
This is the entry point for all transforms.
static bool tryToRecognizeTableBasedCttz(Instruction &I)
static bool foldGuardedFunnelShift(Instruction &I, const DominatorTree &DT)
Match a pattern for a bitwise funnel/rotate operation that partially guards against undefined behavio...
static cl::opt< unsigned > MaxInstrsToScan("aggressive-instcombine-max-scan-instrs", cl::init(64), cl::Hidden, cl::desc("Max number of instructions to scan for aggressive instcombine."))
static bool foldLoadsRecursive(Value *V, LoadOps &LOps, const DataLayout &DL, AliasAnalysis &AA)
static std::pair< APInt, APInt > getStrideAndModOffsetOfGEP(Value *PtrOp, const DataLayout &DL)
static bool isCTTZTable(const ConstantDataArray &Table, uint64_t Mul, uint64_t Shift, uint64_t InputBits)
static bool foldPatternedLoads(Instruction &I, const DataLayout &DL)
If C is a constant patterned array and all valid loaded results for given alignment are same to a con...
static bool foldLibCalls(Instruction &I, TargetTransformInfo &TTI, TargetLibraryInfo &TLI, AssumptionCache &AC, DominatorTree &DT, const DataLayout &DL, bool &MadeCFGChange)
static bool foldUnusualPatterns(Function &F, DominatorTree &DT, TargetTransformInfo &TTI, TargetLibraryInfo &TLI, AliasAnalysis &AA, AssumptionCache &AC, bool &MadeCFGChange)
This is the entry point for folds that could be implemented in regular InstCombine,...
AggressiveInstCombiner - Combine expression patterns to form expressions with fewer,...
This is the interface for LLVM's primary stateless and local alias analysis.
static GCRegistry::Add< OcamlGC > B("ocaml", "ocaml 3.10-compatible GC")
Returns the sub type a function will return at a given Idx Should correspond to the result type of an ExtractValue instruction executed with just that one unsigned Idx
static GCMetadataPrinterRegistry::Add< ErlangGCPrinter > X("erlang", "erlang-compatible garbage collector")
static bool runImpl(Function &F, const TargetLowering &TLI)
This is the interface for a simple mod/ref and alias analysis over globals.
static MaybeAlign getAlign(Value *Ptr)
static Instruction * matchFunnelShift(Instruction &Or, InstCombinerImpl &IC)
Match UB-safe variants of the funnel shift intrinsic.
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
static const MCExpr * MaskShift(const MCExpr *Val, uint32_t Mask, uint32_t Shift, MCContext &Ctx)
This file defines the 'Statistic' class, which is designed to be an easy way to expose various metric...
#define STATISTIC(VARNAME, DESC)
A manager for alias analyses.
ModRefInfo getModRefInfo(const Instruction *I, const std::optional< MemoryLocation > &OptLoc)
Check whether or not an instruction may read or write the optionally specified memory location.
Class for arbitrary precision integers.
uint64_t getZExtValue() const
Get zero extended value.
void setBit(unsigned BitPosition)
Set the given bit to 1 whose position is given as "bitPosition".
unsigned getBitWidth() const
Return the number of bits in the APInt.
bool isNegative() const
Determine sign of this APInt.
static APInt getSplat(unsigned NewLen, const APInt &V)
Return a value containing V broadcasted over NewLen bits.
APInt srem(const APInt &RHS) const
Function for signed remainder operation.
bool slt(const APInt &RHS) const
Signed less than comparison.
static APInt getBitsSetFrom(unsigned numBits, unsigned loBit)
Constructs an APInt value that has a contiguous range of bits set.
static APInt getOneBitSet(unsigned numBits, unsigned BitNo)
Return an APInt with exactly one bit set in the result.
bool uge(const APInt &RHS) const
Unsigned greater or equal comparison.
PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM)
A container for analyses that lazily runs them and caches their results.
PassT::Result & getResult(IRUnitT &IR, ExtraArgTs... ExtraArgs)
Get the result of an analysis pass for a given IR unit.
A function analysis which provides an AssumptionCache.
A cache of @llvm.assume calls within a function.
LLVM Basic Block Representation.
iterator begin()
Instruction iterator methods.
const_iterator getFirstInsertionPt() const
Returns an iterator to the first instruction in this block that is suitable for inserting a non-PHI i...
static BasicBlock * Create(LLVMContext &Context, const Twine &Name="", Function *Parent=nullptr, BasicBlock *InsertBefore=nullptr)
Creates a new BasicBlock.
const Function * getParent() const
Return the enclosing method, or null if none.
const Instruction * getTerminator() const LLVM_READONLY
Returns the terminator instruction if the block is well formed or null if the block is not well forme...
Represents analyses that only rely on functions' control flow.
This class represents a function call, abstracting a target machine's calling convention.
Predicate
This enumeration lists the possible predicates for CmpInst subclasses.
An array constant whose element type is a simple 1/2/4/8-byte integer or float/double,...
uint64_t getElementAsInteger(unsigned i) const
If this is a sequential container of integers (of any size), return the specified element in the low ...
unsigned getNumElements() const
Return the number of elements in the array or vector.
This is the shared class of boolean and integer constants.
This is an important base class in LLVM.
static Constant * getNullValue(Type *Ty)
Constructor to create a '0' constant of arbitrary type.
A parsed version of the target data layout string in and methods for querying it.
Analysis pass which computes a DominatorTree.
Concrete subclass of DominatorTreeBase that is used to compute a normal dominator tree.
bool isReachableFromEntry(const Use &U) const
Provide an overload for a Use.
bool dominates(const BasicBlock *BB, const Use &U) const
Return true if the (end of the) basic block BB dominates the use U.
void applyUpdates(ArrayRef< typename DomTreeT::UpdateType > Updates)
Submit updates to all available trees.
an instruction for type-safe pointer arithmetic to access elements of arrays and structs
const Constant * getInitializer() const
getInitializer - Return the initializer for this global variable.
bool hasInitializer() const
Definitions have initializers, declarations don't.
bool isConstant() const
If the value is a global constant, its value is immutable throughout the runtime execution of the pro...
LoadInst * CreateAlignedLoad(Type *Ty, Value *Ptr, MaybeAlign Align, const char *Name)
Value * CreateSExt(Value *V, Type *DestTy, const Twine &Name="")
Value * CreateFreeze(Value *V, const Twine &Name="")
Value * CreatePtrAdd(Value *Ptr, Value *Offset, const Twine &Name="", GEPNoWrapFlags NW=GEPNoWrapFlags::none())
void setFastMathFlags(FastMathFlags NewFMF)
Set the fast-math flags to be used with generated fp-math operators.
ConstantInt * getInt32(uint32_t C)
Get a constant 32-bit value.
PHINode * CreatePHI(Type *Ty, unsigned NumReservedValues, const Twine &Name="")
SwitchInst * CreateSwitch(Value *V, BasicBlock *Dest, unsigned NumCases=10, MDNode *BranchWeights=nullptr, MDNode *Unpredictable=nullptr)
Create a switch instruction with the specified value, default dest, and with a hint for the number of...
Value * CreateICmpEQ(Value *LHS, Value *RHS, const Twine &Name="")
Value * CreateShl(Value *LHS, Value *RHS, const Twine &Name="", bool HasNUW=false, bool HasNSW=false)
Value * CreateZExt(Value *V, Type *DestTy, const Twine &Name="", bool IsNonNeg=false)
Value * CreateAnd(Value *LHS, Value *RHS, const Twine &Name="")
Value * CreateIsNotNull(Value *Arg, const Twine &Name="")
Return a boolean value testing if Arg != 0.
Value * CreateTrunc(Value *V, Type *DestTy, const Twine &Name="", bool IsNUW=false, bool IsNSW=false)
BranchInst * CreateBr(BasicBlock *Dest)
Create an unconditional 'br label X' instruction.
void SetInsertPoint(BasicBlock *TheBB)
This specifies that created instructions should be appended to the end of the specified block.
CallInst * CreateCall(FunctionType *FTy, Value *Callee, ArrayRef< Value * > Args=std::nullopt, const Twine &Name="", MDNode *FPMathTag=nullptr)
Value * CreateInBoundsPtrAdd(Value *Ptr, Value *Offset, const Twine &Name="")
IntegerType * getInt8Ty()
Fetch the type representing an 8-bit integer.
This provides a uniform API for creating instructions and inserting them into a basic block: either a...
void setAAMetadata(const AAMDNodes &N)
Sets the AA metadata on this instruction from the AAMDNodes structure.
InstListType::iterator eraseFromParent()
This method unlinks 'this' from the containing basic block and deletes it.
AAMDNodes getAAMetadata() const
Returns the AA metadata for this instruction.
Class to represent integer types.
static IntegerType * get(LLVMContext &C, unsigned NumBits)
This static method is the primary way of constructing an IntegerType.
An instruction for reading from memory.
unsigned getPointerAddressSpace() const
Returns the address space of the pointer operand.
Value * getPointerOperand()
This class implements a map that also provides access to all stored values in a deterministic order.
Representation for a specific memory location.
MemoryLocation getWithNewSize(LocationSize NewSize) const
static MemoryLocation get(const LoadInst *LI)
Return a location with information about the memory reference by the given instruction.
A Module instance is used to store all the information related to an LLVM module.
void addIncoming(Value *V, BasicBlock *BB)
Add an incoming value to the end of the PHI list.
static PHINode * Create(Type *Ty, unsigned NumReservedValues, const Twine &NameStr="", InsertPosition InsertBefore=nullptr)
Constructors - NumReservedValues is a hint for the number of incoming edges that this phi node will h...
A set of analyses that are preserved following a run of a transformation pass.
static PreservedAnalyses all()
Construct a special preserved set that preserves all passes.
void preserveSet()
Mark an analysis set as preserved.
void preserve()
Mark an analysis as preserved.
std::pair< iterator, bool > insert(PtrType Ptr)
Inserts Ptr if and only if there is no element in the container equal to Ptr.
SmallPtrSet - This class implements a set which is optimized for holding SmallSize or less elements.
void push_back(const T &Elt)
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
StringRef - Represent a constant reference to a string, i.e.
static constexpr size_t npos
Analysis pass providing the TargetTransformInfo.
Analysis pass providing the TargetLibraryInfo.
Provides information about what library functions are available for the current target.
bool getLibFunc(StringRef funcName, LibFunc &F) const
Searches for a particular function name.
bool run(Function &F)
Perform TruncInst pattern optimization on given function.
Twine - A lightweight data structure for efficiently representing the concatenation of temporary valu...
The instances of the Type class are immutable: once they are created, they are never changed.
bool isIntOrIntVectorTy() const
Return true if this is an integer type or a vector of integer types.
unsigned getScalarSizeInBits() const LLVM_READONLY
If this is a vector type, return the getPrimitiveSizeInBits value for the element type.
LLVMContext & getContext() const
Return the LLVMContext in which this type was uniqued.
bool isIntegerTy() const
True if this is an instance of IntegerType.
TypeSize getPrimitiveSizeInBits() const LLVM_READONLY
Return the basic size of this type if it is a primitive type.
LLVM Value Representation.
Type * getType() const
All values are typed, get the type of this value.
const Value * stripAndAccumulateConstantOffsets(const DataLayout &DL, APInt &Offset, bool AllowNonInbounds, bool AllowInvariantGroup=false, function_ref< bool(Value &Value, APInt &Offset)> ExternalAnalysis=nullptr) const
Accumulate the constant offset this value has compared to a base pointer.
void replaceAllUsesWith(Value *V)
Change all uses of this to point to a new Value.
LLVMContext & getContext() const
All values hold a context through their type.
uint64_t getPointerDereferenceableBytes(const DataLayout &DL, bool &CanBeNull, bool &CanBeFreed) const
Returns the number of bytes known to be dereferenceable for the pointer value.
StringRef getName() const
Return a constant reference to the value's name.
void takeName(Value *V)
Transfer the name from V to this value.
const ParentTy * getParent() const
APInt GreatestCommonDivisor(APInt A, APInt B)
Compute GCD of two unsigned APInt values.
@ Fast
Attempts to make calls as fast as possible (e.g.
@ C
The default llvm calling convention, compatible with C.
Function * getDeclaration(Module *M, ID id, ArrayRef< Type * > Tys=std::nullopt)
Create or insert an LLVM Function declaration for an intrinsic, and return it.
BinaryOp_match< LHS, RHS, Instruction::And > m_And(const LHS &L, const RHS &R)
BinaryOp_match< LHS, RHS, Instruction::And, true > m_c_And(const LHS &L, const RHS &R)
Matches an And with LHS and RHS in either order.
specific_intval< false > m_SpecificInt(const APInt &V)
Match a specific integer value or vector with all elements equal to the value.
match_combine_or< CastInst_match< OpTy, ZExtInst >, OpTy > m_ZExtOrSelf(const OpTy &Op)
bool match(Val *V, const Pattern &P)
bind_ty< Instruction > m_Instruction(Instruction *&I)
Match an instruction, capturing it if we match.
specificval_ty m_Specific(const Value *V)
Match if we have a specific specified value.
class_match< ConstantInt > m_ConstantInt()
Match an arbitrary ConstantInt and ignore it.
cst_pred_ty< is_one > m_One()
Match an integer 1 or a vector with all elements equal to 1.
MaxMin_match< ICmpInst, LHS, RHS, smin_pred_ty > m_SMin(const LHS &L, const RHS &R)
BinaryOp_match< LHS, RHS, Instruction::Mul > m_Mul(const LHS &L, const RHS &R)
deferredval_ty< Value > m_Deferred(Value *const &V)
Like m_Specific(), but works if the specific value to match is determined as part of the same match()...
cst_pred_ty< is_zero_int > m_ZeroInt()
Match an integer 0 or a vector with all elements equal to 0.
CmpClass_match< LHS, RHS, ICmpInst, ICmpInst::Predicate > m_ICmp(ICmpInst::Predicate &Pred, const LHS &L, const RHS &R)
OneUse_match< T > m_OneUse(const T &SubPattern)
BinaryOp_match< cst_pred_ty< is_zero_int >, ValTy, Instruction::Sub > m_Neg(const ValTy &V)
Matches a 'Neg' as 'sub 0, V'.
specific_bbval m_SpecificBB(BasicBlock *BB)
Match a specific basic block value.
CastInst_match< OpTy, ZExtInst > m_ZExt(const OpTy &Op)
Matches ZExt.
brc_match< Cond_t, bind_ty< BasicBlock >, bind_ty< BasicBlock > > m_Br(const Cond_t &C, BasicBlock *&T, BasicBlock *&F)
BinaryOp_match< LHS, RHS, Instruction::Add, true > m_c_Add(const LHS &L, const RHS &R)
Matches a Add with LHS and RHS in either order.
CastInst_match< OpTy, FPToSIInst > m_FPToSI(const OpTy &Op)
MaxMin_match< ICmpInst, LHS, RHS, smax_pred_ty > m_SMax(const LHS &L, const RHS &R)
apint_match m_APInt(const APInt *&Res)
Match a ConstantInt or splatted ConstantVector, binding the specified pointer to the contained APInt.
class_match< Value > m_Value()
Match an arbitrary value and ignore it.
BinaryOp_match< LHS, RHS, Instruction::LShr > m_LShr(const LHS &L, const RHS &R)
BinaryOp_match< LHS, RHS, Instruction::Shl > m_Shl(const LHS &L, const RHS &R)
BinaryOp_match< LHS, RHS, Instruction::Or > m_Or(const LHS &L, const RHS &R)
BinaryOp_match< LHS, RHS, Instruction::Or, true > m_c_Or(const LHS &L, const RHS &R)
Matches an Or with LHS and RHS in either order.
BinaryOp_match< LHS, RHS, Instruction::Sub > m_Sub(const LHS &L, const RHS &R)
initializer< Ty > init(const Ty &Val)
NodeAddr< PhiNode * > Phi
NodeAddr< FuncNode * > Func
This is an optimization pass for GlobalISel generic memory operations.
bool isOnlyUsedInZeroComparison(const Instruction *CxtI)
bool getConstantStringInfo(const Value *V, StringRef &Str, bool TrimAtNul=true)
This function computes the length of a null-terminated C string pointed to by V.
iterator_range< T > make_range(T x, T y)
Convenience function for iterating over sub-ranges.
const Value * getUnderlyingObject(const Value *V, unsigned MaxLookup=6)
This method strips off any GEP address adjustments, pointer casts or llvm.threadlocal....
iterator_range< early_inc_iterator_impl< detail::IterOfRange< RangeT > > > make_early_inc_range(RangeT &&Range)
Make a range that does early increment to allow mutation of the underlying range without disrupting i...
bool SimplifyInstructionsInBlock(BasicBlock *BB, const TargetLibraryInfo *TLI=nullptr)
Scan the specified basic block and try to simplify any instructions in it and recursively delete dead...
constexpr bool isPowerOf2_64(uint64_t Value)
Return true if the argument is a power of two > 0 (64 bit edition.)
bool isLibFuncEmittable(const Module *M, const TargetLibraryInfo *TLI, LibFunc TheLibFunc)
Check whether the library function is available on target and also that it in the current Module is a...
unsigned Log2_32(uint32_t Value)
Return the floor log base 2 of the specified value, -1 if the value is zero.
auto reverse(ContainerTy &&C)
constexpr bool isPowerOf2_32(uint32_t Value)
Return true if the argument is a power of two > 0.
bool isModSet(const ModRefInfo MRI)
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
Constant * ConstantFoldLoadFromConst(Constant *C, Type *Ty, const APInt &Offset, const DataLayout &DL)
Extract value of C at the given Offset reinterpreted as Ty.
@ And
Bitwise or logical AND of integers.
constexpr unsigned BitWidth
BasicBlock * SplitBlock(BasicBlock *Old, BasicBlock::iterator SplitPt, DominatorTree *DT, LoopInfo *LI=nullptr, MemorySSAUpdater *MSSAU=nullptr, const Twine &BBName="", bool Before=false)
Split the specified block at the specified instruction.
bool cannotBeOrderedLessThanZero(const Value *V, unsigned Depth, const SimplifyQuery &SQ)
Return true if we can prove that the specified FP value is either NaN or never less than -0....
bool isGuaranteedNotToBePoison(const Value *V, AssumptionCache *AC=nullptr, const Instruction *CtxI=nullptr, const DominatorTree *DT=nullptr, unsigned Depth=0)
Returns true if V cannot be poison, but may be undef.
void swap(llvm::BitVector &LHS, llvm::BitVector &RHS)
Implement std::swap in terms of BitVector swap.
This is used by foldLoadsRecursive() to capture a Root Load node which is of type or(load,...
This is used by foldAnyOrAllBitsSet() to capture a source value (Root) and the bit indexes (Mask) nee...
MaskOps(unsigned BitWidth, bool MatchAnds)
A collection of metadata nodes that might be associated with a memory access used by the alias-analys...
AAMDNodes concat(const AAMDNodes &Other) const
Determine the best AAMDNodes after concatenating two different locations together.