1//===- llvm/Analysis/IVDescriptors.cpp - IndVar Descriptors -----*- C++ -*-===// 3// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. 4// See https://llvm.org/LICENSE.txt for license information. 5// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception 7//===----------------------------------------------------------------------===// 9// This file "describes" induction and recurrence variables. 11//===----------------------------------------------------------------------===// 29#define DEBUG_TYPE "iv-descriptors" 33for (
constUse &
Use :
I->operands())
34if (!Set.count(dyn_cast<Instruction>(
Use)))
65/// Determines if Phi may have been type-promoted. If Phi has a single user 66/// that ANDs the Phi with a type mask, return the user. RT is updated to 67/// account for the narrower bit width represented by the mask, and the AND 68/// instruction is added to CI. 75constAPInt *M =
nullptr;
76Instruction *
I, *J = cast<Instruction>(Phi->use_begin()->getUser());
78// Matches either I & 2^x-1 or 2^x-1 & I. If we find a match, we update RT 79// with a new integer type of the corresponding bit width. 81 int32_t Bits = (*M + 1).exactLogBase2();
92/// Compute the minimal bit width needed to represent a reduction whose exit 93/// instruction is given by Exit. 100uint64_t MaxBitWidth =
DL.getTypeSizeInBits(Exit->getType());
103// Use the demanded bits analysis to determine the bits that are live out 104// of the exit instruction, rounding up to the nearest power of two. If the 105// use of demanded bits results in a smaller bit width, we know the value 106// must be positive (i.e., IsSigned = false), because if this were not the 107// case, the sign bit would have been demanded. 108auto Mask = DB->getDemandedBits(Exit);
109 MaxBitWidth = Mask.getBitWidth() - Mask.countl_zero();
112if (MaxBitWidth ==
DL.getTypeSizeInBits(Exit->getType()) && AC && DT) {
113// If demanded bits wasn't able to limit the bit width, we can try to use 114// value tracking instead. This can be the case, for example, if the value 117auto NumTypeBits =
DL.getTypeSizeInBits(Exit->getType());
118 MaxBitWidth = NumTypeBits - NumSignBits;
120if (!Bits.isNonNegative()) {
121// If the value is not known to be non-negative, we set IsSigned to true, 122// meaning that we will use sext instructions instead of zext 123// instructions to restore the original type. 125// Make sure at least one sign bit is included in the result, so it 126// will get properly sign-extended. 136/// Collect cast instructions that can be ignored in the vectorizer's cost 137/// model, given a reduction exit value and the minimal type in which the 138// reduction can be represented. Also search casts to the recurrence type 139// to find the minimum width used by the recurrence. 143unsigned &MinWidthCastToRecurTy) {
148 MinWidthCastToRecurTy = -1U;
150while (!Worklist.
empty()) {
153if (
auto *Cast = dyn_cast<CastInst>(Val)) {
154if (Cast->getSrcTy() == RecurrenceType) {
155// If the source type of a cast instruction is equal to the recurrence 156// type, it will be eliminated, and should be ignored in the vectorizer 161if (Cast->getDestTy() == RecurrenceType) {
162// The minimum width used by the recurrence is found by checking for 163// casts on its operands. The minimum width is used by the vectorizer 164// when finding the widest type for in-loop reductions without any 166 MinWidthCastToRecurTy = std::min<unsigned>(
167 MinWidthCastToRecurTy, Cast->getSrcTy()->getScalarSizeInBits());
171// Add all operands to the work list if they are loop-varying values that 172// we haven't yet visited. 173for (
Value *O : cast<User>(Val)->operands())
174if (
auto *
I = dyn_cast<Instruction>(O))
180// Check if a given Phi node can be recognized as an ordered reduction for 181// vectorizing floating point operations without unsafe math. 184// Currently only FAdd and FMulAdd are supported. 195// Ensure the exit instruction has only one user other than the reduction PHI 196if (Exit != ExactFPMathInst || Exit->hasNUsesOrMore(3))
199// The only pattern accepted is the one in which the reduction PHI 200// is used as one of the operands of the exit instruction 201auto *Op0 = Exit->getOperand(0);
202auto *Op1 = Exit->getOperand(1);
208LLVM_DEBUG(
dbgs() <<
"LV: Found an ordered reduction: Phi: " << *Phi
209 <<
", ExitInst: " << *Exit <<
"\n");
218if (Phi->getNumIncomingValues() != 2)
221// Reduction variables are only found in the loop header block. 222if (Phi->getParent() != TheLoop->
getHeader())
225// Obtain the reduction start value from the value that comes from the loop 229// ExitInstruction is the single value which is used outside the loop. 230// We only allow for a single reduction value to be used outside the loop. 231// This includes users of the reduction, variables (which form a cycle 232// which ends in the phi node). 235// Variable to keep last visited store instruction. By the end of the 236// algorithm this variable will be either empty or having intermediate 237// reduction value stored in invariant address. 240// Indicates that we found a reduction operation in our scan. 241bool FoundReduxOp =
false;
243// We start with the PHI node and scan for all of the users of this 244// instruction. All users must be instructions that can be used as reduction 245// variables (such as ADD). We must have a single out-of-block user. The cycle 246// must include the original PHI. 247bool FoundStartPHI =
false;
249// To recognize min/max patterns formed by a icmp select sequence, we store 250// the number of instruction we saw from the recognized min/max pattern, 251// to make sure we only see exactly the two instructions. 252unsigned NumCmpSelectPatternInst = 0;
255// Data used for determining if the recurrence has been type-promoted. 256Type *RecurrenceType = Phi->getType();
258unsigned MinWidthCastToRecurrenceType;
265// Return early if the recurrence kind does not match the type of Phi. If the 266// recurrence kind is arithmetic, we attempt to look through AND operations 267// resulting from the type promotion performed by InstCombine. Vector 268// operations are not limited to the legal integer widths, so we may be able 269// to evaluate the reduction in the narrower width. 277 Start =
lookThroughAnd(Phi, RecurrenceType, VisitedInsts, CastInsts);
279// Pointer min/max may exist, but it is not supported as a reduction op. 284 VisitedInsts.
insert(Start);
286// Start with all flags set because we will intersect this with the reduction 287// flags from all the reduction operations. 290// The first instruction in the use-def chain of the Phi node that requires 291// exact floating point operations. 294// A value in the reduction can be used: 295// - By the reduction: 296// - Reduction operation: 297// - One use of reduction value (safe). 298// - Multiple use of reduction value (not safe). 300// - All uses of the PHI must be the reduction (safe). 301// - Otherwise, not safe. 302// - By instructions outside of the loop (safe). 303// * One value may have several outside users, but all outside 304// uses must be of the same value. 305// - By store instructions with a loop invariant address (safe with 306// the following restrictions): 307// * If there are several stores, all must have the same address. 308// * Final value should be stored in that loop invariant address. 309// - By an instruction that is not part of the reduction (not safe). 311// * An instruction type other than PHI or the reduction operation. 312// * A PHI in the header other than the initial PHI. 313while (!Worklist.
empty()) {
316// Store instructions are allowed iff it is the store of the reduction 317// value to the same loop invariant memory location. 318if (
auto *SI = dyn_cast<StoreInst>(Cur)) {
320LLVM_DEBUG(
dbgs() <<
"Store instructions are not processed without " 321 <<
"Scalar Evolution Analysis\n");
325constSCEV *PtrScev = SE->
getSCEV(SI->getPointerOperand());
326// Check it is the same address as previous stores 328constSCEV *OtherScev =
331if (OtherScev != PtrScev) {
332LLVM_DEBUG(
dbgs() <<
"Storing reduction value to different addresses " 333 <<
"inside the loop: " << *SI->getPointerOperand()
340// Check the pointer is loop invariant 342LLVM_DEBUG(
dbgs() <<
"Storing reduction value to non-uniform address " 343 <<
"inside the loop: " << *SI->getPointerOperand()
348// IntermediateStore is always the last store in the loop. 354// If the instruction has no users then this is a broken chain and can't be 355// a reduction variable. 359bool IsAPhi = isa<PHINode>(Cur);
361// A header PHI use other than the original PHI. 362if (Cur != Phi && IsAPhi && Cur->
getParent() == Phi->getParent())
365// Reductions of instructions such as Div, and Sub is only possible if the 366// LHS is the reduction variable. 367if (!Cur->
isCommutative() && !IsAPhi && !isa<SelectInst>(Cur) &&
368 !isa<ICmpInst>(Cur) && !isa<FCmpInst>(Cur) &&
372// Any reduction instruction must be of one of the allowed kinds. We ignore 373// the starting value (the Phi or an AND instruction if the Phi has been 378 ExactFPMathInst = ExactFPMathInst ==
nullptr 383// FIXME: FMF is allowed on phi, but propagation is not handled correctly. 386if (
auto *Sel = dyn_cast<SelectInst>(ReduxDesc.
getPatternInst())) {
387// Accept FMF on either fcmp or select of a min/max idiom. 388// TODO: This is a hack to work-around the fact that FMF may not be 389// assigned/propagated correctly. If that problem is fixed or we 390// standardize on fmin/fmax via intrinsics, this can be removed. 391if (
auto *FCmp = dyn_cast<FCmpInst>(Sel->getCondition()))
392 CurFMF |= FCmp->getFastMathFlags();
396// Update this reduction kind if we matched a new instruction. 397// TODO: Can we eliminate the need for a 2nd InstDesc by keeping 'Kind' 398// state accurate while processing the worklist? 403bool IsASelect = isa<SelectInst>(Cur);
405// A conditional reduction operation must only have 2 or less uses in 411// A reduction operation must only have one use of the reduction value. 416// All inputs to a PHI node must be a reduction value. 417if (IsAPhi && Cur != Phi && !
areAllUsesIn(Cur, VisitedInsts))
421 (isa<ICmpInst>(Cur) || isa<SelectInst>(Cur)))
422 ++NumCmpSelectPatternInst;
424 (isa<FCmpInst>(Cur) || isa<SelectInst>(Cur)))
425 ++NumCmpSelectPatternInst;
427// Check whether we found a reduction operator. 428 FoundReduxOp |= !IsAPhi && Cur != Start;
430// Process users of current instruction. Push non-PHI nodes after PHI nodes 431// onto the stack. This way we are going to have seen all inputs to PHI 432// nodes once we get to them. 438// If the user is a call to llvm.fmuladd then the instruction can only be 444// Check if we found the exit user. 447// If we already know this instruction is used externally, move on to 449if (ExitInstruction == Cur)
452// Exit if you find multiple values used outside or if the header phi 453// node is being used. In this case the user uses the value of the 454// previous iteration, in which case we would loose "VF-1" iterations of 455// the reduction operation if we vectorize. 456if (ExitInstruction !=
nullptr || Cur == Phi)
459// The instruction used by an outside user must be the last instruction 460// before we feed back to the reduction phi. Otherwise, we loose VF-1 461// operations on the value. 465 ExitInstruction = Cur;
469// Process instructions only once (termination). Each reduction cycle 470// value must only be used once, except by phi nodes and min/max 471// reductions which are represented as a cmp followed by a select. 473if (VisitedInsts.
insert(UI).second) {
474if (isa<PHINode>(UI)) {
478if (SI && SI->getPointerOperand() == Cur) {
479// Reduction variable chain can only be stored somewhere but it 480// can't be used as an address. 485 }
elseif (!isa<PHINode>(UI) &&
486 ((!isa<FCmpInst>(UI) && !isa<ICmpInst>(UI) &&
487 !isa<SelectInst>(UI)) ||
494// Remember that we completed the cycle. 502// This means we have seen one but not the other instruction of the 503// pattern or more than just a select and cmp. Zero implies that we saw a 504// llvm.min/max intrinsic, which is always OK. 506 NumCmpSelectPatternInst != 0)
513// Check that stored value goes to the phi node again. This way we make sure 514// that the value stored in IntermediateStore is indeed the final reduction 522// If there is an exit instruction it's value should be stored in 524if (ExitInstruction &&
526LLVM_DEBUG(
dbgs() <<
"Last store Instruction of reduction value does not " 527"store last calculated value of the reduction: " 532// If all uses are inside the loop (intermediate stores), then the 533// reduction value after the loop will be the one used in the last store. 538if (!FoundStartPHI || !FoundReduxOp || !ExitInstruction)
545// If the starting value is not the same as the phi node, we speculatively 546// looked through an 'and' instruction when evaluating a potential 547// arithmetic reduction to determine if it may have been type-promoted. 549// We now compute the minimal bit width that is required to represent the 550// reduction. If this is the same width that was indicated by the 'and', we 551// can represent the reduction in the smaller type. The 'and' instruction 552// will be eliminated since it will essentially be a cast instruction that 553// can be ignore in the cost model. If we compute a different type than we 554// did when evaluating the 'and', the 'and' will not be eliminated, and we 555// will end up with different kinds of operations in the recurrence 556// expression (e.g., IntegerAND, IntegerADD). We give up if this is 559// The vectorizer relies on InstCombine to perform the actual 560// type-shrinking. It does this by inserting instructions to truncate the 561// exit value of the reduction to the width indicated by RecurrenceType and 562// then extend this value back to the original width. If IsSigned is false, 563// a 'zext' instruction will be generated; otherwise, a 'sext' will be 566// TODO: We should not rely on InstCombine to rewrite the reduction in the 567// smaller type. We should just generate a correctly typed expression 570 std::tie(ComputedType, IsSigned) =
572if (ComputedType != RecurrenceType)
576// Collect cast instructions and the minimum width used by the recurrence. 577// If the starting value is not the same as the phi node and the computed 578// recurrence type is equal to the recurrence type, the recurrence expression 579// will be represented in a narrower or wider type. If there are any cast 580// instructions that will be unnecessary, collect them in CastsFromRecurTy. 581// Note that the 'and' instruction was already included in this list. 583// TODO: A better way to represent this may be to tag in some way all the 584// instructions that are a part of the reduction. The vectorizer cost 585// model could then apply the recurrence type to these instructions, 586// without needing a white list of instructions to ignore. 587// This may also be useful for the inloop reductions, if it can be 588// kept simple enough. 590 MinWidthCastToRecurrenceType);
592// We found a reduction var if we have reached the original phi node and we 593// only have a single instruction with out-of-loop users. 595// The ExitInstruction(Instruction which is allowed to have out-of-loop users) 596// is saved as part of the RecurrenceDescriptor. 598// Save the description of this reduction variable. 600 FMF, ExactFPMathInst, RecurrenceType, IsSigned,
601 IsOrdered, CastInsts, MinWidthCastToRecurrenceType);
607// We are looking for loops that do something like this: 609// for (int i = 0; i < n; i++) { 613// where the reduction value (r) only has two states, in this example 0 or 3. 614// The generated LLVM IR for this type of loop will be like this: 616// %r = phi i32 [ %spec.select, %for.body ], [ 0, %entry ] 618// %cmp = icmp sgt i32 %5, 3 619// %spec.select = select i1 %cmp, i32 3, i32 %r 621// In general we can support vectorization of loops where 'r' flips between 622// any two non-constants, provided they are loop invariant. The only thing 623// we actually care about at the end of the loop is whether or not any lane 624// in the selected vector is different from the start value. The final 625// across-vector reduction after the loop simply involves choosing the start 626// value if nothing changed (0 in the example above) or the other selected 627// value (3 in the example above). 631// We must handle the select(cmp(),x,y) as a single instruction. Advance to 635if (
auto *
Select = dyn_cast<SelectInst>(*
I->user_begin()))
644Value *NonPhi =
nullptr;
646if (OrigPhi == dyn_cast<PHINode>(SI->getTrueValue()))
647 NonPhi = SI->getFalseValue();
648elseif (OrigPhi == dyn_cast<PHINode>(SI->getFalseValue()))
649 NonPhi = SI->getTrueValue();
653// We are looking for selects of the form: 654// select(cmp(), phi, loop_invariant) or 655// select(cmp(), loop_invariant, phi) 663// We are looking for loops that do something like this: 665// for (int i = 0; i < n; i++) { 669// The reduction value (r) is derived from either the values of an increasing 670// induction variable (i) sequence, or from the start value (0). 671// The LLVM IR generated for such loops would be as follows: 673// %r = phi i32 [ %spec.select, %for.body ], [ 0, %entry ] 674// %i = phi i32 [ %inc, %for.body ], [ 0, %entry ] 676// %cmp = icmp sgt i32 %5, 3 677// %spec.select = select i1 %cmp, i32 %i, i32 %r 678// %inc = add nsw i32 %i, 1 680// Since 'i' is an increasing induction variable, the reduction value after the 681// loop will be the maximum value of 'i' that the condition (src[i] > 3) is 682// satisfied, or the start value (0 in the example above). When the start value 683// of the increasing induction variable 'i' is greater than the minimum value of 684// the data type, we can use the minimum value of the data type as a sentinel 685// value to replace the start value. This allows us to perform a single 686// reduction max operation to obtain the final reduction result. 687// TODO: It is possible to solve the case where the start value is the minimum 688// value of the data type or a non-constant value by using mask and multiple 689// reduction operations. 693// TODO: Support the vectorization of FindLastIV when the reduction phi is 694// used by more than one select instruction. This vectorization is only 695// performed when the SCEV of each increasing induction variable used by the 696// select instructions is identical. 700// TODO: Match selects with multi-use cmp conditions. 701Value *NonRdxPhi =
nullptr;
708auto IsIncreasingLoopInduction = [&](
Value *V) {
709Type *Ty = V->getType();
713auto *AR = dyn_cast<SCEVAddRecExpr>(SE.
getSCEV(V));
714if (!AR || AR->getLoop() != TheLoop)
717constSCEV *Step = AR->getStepRecurrence(SE);
723// Keep the minimum value of the recurrence type as the sentinel value. 724// The maximum acceptable range for the increasing induction variable, 725// called the valid range, will be defined as 726// [<sentinel value> + 1, <sentinel value>) 727// where <sentinel value> is SignedMin(<recurrence type>) 728// TODO: This range restriction can be lifted by adding an additional 729// virtual OR reduction. 734 <<
", and the signed range of " << *AR <<
" is " 736// Ensure the induction variable does not wrap around by verifying that its 737// range is fully contained within the valid range. 741// We are looking for selects of the form: 742// select(cmp(), phi, increasing_loop_induction) or 743// select(cmp(), increasing_loop_induction, phi) 744// TODO: Support for monotonically decreasing induction variable 745if (!IsIncreasingLoopInduction(NonRdxPhi))
755assert((isa<CmpInst>(
I) || isa<SelectInst>(
I) || isa<CallInst>(
I)) &&
756"Expected a cmp or select or call instruction");
760// We must handle the select(cmp()) as a single instruction. Advance to the 764if (
auto *
Select = dyn_cast<SelectInst>(*
I->user_begin()))
768// Only match select with single use cmp condition, or a min/max intrinsic. 769if (!isa<IntrinsicInst>(
I) &&
774// Look for a min/max pattern. 799/// Returns true if the select instruction has users in the compare-and-add 800/// reduction pattern below. The select instruction argument is the last one 805/// %cmp = fcmp pred %0, %CFP 806/// %add = fadd %0, %sum.1 807/// %sum.2 = select %cmp, %add, %sum.1 814CmpInst *CI = dyn_cast<CmpInst>(SI->getCondition());
815// Only handle single use cases for now. 819Value *TrueVal = SI->getTrueValue();
820Value *FalseVal = SI->getFalseValue();
821// Handle only when either of operands of select instruction is a PHI 823if ((isa<PHINode>(TrueVal) && isa<PHINode>(FalseVal)) ||
824 (!isa<PHINode>(TrueVal) && !isa<PHINode>(FalseVal)))
827Instruction *I1 = isa<PHINode>(TrueVal) ? dyn_cast<Instruction>(FalseVal)
828 : dyn_cast<Instruction>(TrueVal);
829if (!I1 || !I1->isBinaryOp())
842Instruction *IPhi = isa<PHINode>(Op1) ? dyn_cast<Instruction>(Op1)
843 : dyn_cast<Instruction>(Op2);
844if (!IPhi || IPhi != FalseVal)
854switch (
I->getOpcode()) {
857case Instruction::PHI:
859case Instruction::Sub:
860case Instruction::Add:
862case Instruction::Mul:
864case Instruction::And:
868case Instruction::Xor:
870case Instruction::FDiv:
871case Instruction::FMul:
873I->hasAllowReassoc() ?
nullptr :
I);
874case Instruction::FSub:
875case Instruction::FAdd:
877I->hasAllowReassoc() ?
nullptr :
I);
878case Instruction::Select:
885case Instruction::FCmp:
886case Instruction::ICmp:
887case Instruction::Call:
890auto HasRequiredFMF = [&]() {
893if (isa<FPMathOperator>(
I) &&
I->hasNoNaNs() &&
I->hasNoSignedZeros())
895// minimum and maximum intrinsics do not require nsz and nnan flags since 896// NaN and signed zeroes are propagated in the intrinsic implementation. 905I->hasAllowReassoc() ?
nullptr :
I);
912unsigned MaxNumUses) {
914for (
constUse &U :
I->operands()) {
915if (Insts.
count(dyn_cast<Instruction>(U)))
917if (NumUses > MaxNumUses)
933F.getFnAttribute(
"no-nans-fp-math").getValueAsBool());
935F.getFnAttribute(
"no-signed-zeros-fp-math").getValueAsBool());
984LLVM_DEBUG(
dbgs() <<
"Found an integer conditional select reduction PHI." 994 <<
"FindLastIV reduction PHI." << *Phi <<
"\n");
999LLVM_DEBUG(
dbgs() <<
"Found an FMult reduction PHI." << *Phi <<
"\n");
1004LLVM_DEBUG(
dbgs() <<
"Found an FAdd reduction PHI." << *Phi <<
"\n");
1009LLVM_DEBUG(
dbgs() <<
"Found a float MAX reduction PHI." << *Phi <<
"\n");
1014LLVM_DEBUG(
dbgs() <<
"Found a float MIN reduction PHI." << *Phi <<
"\n");
1019LLVM_DEBUG(
dbgs() <<
"Found a float conditional select reduction PHI." 1020 <<
" PHI." << *Phi <<
"\n");
1025LLVM_DEBUG(
dbgs() <<
"Found an FMulAdd reduction PHI." << *Phi <<
"\n");
1030LLVM_DEBUG(
dbgs() <<
"Found a float MAXIMUM reduction PHI." << *Phi <<
"\n");
1035LLVM_DEBUG(
dbgs() <<
"Found a float MINIMUM reduction PHI." << *Phi <<
"\n");
1038// Not a reduction of known type. 1045// Ensure the phi node is in the loop header and has two incoming values. 1046if (Phi->getParent() != TheLoop->
getHeader() ||
1047 Phi->getNumIncomingValues() != 2)
1050// Ensure the loop has a preheader and a single latch block. The loop 1051// vectorizer will need the latch to set up the next iteration of the loop. 1054if (!Preheader || !Latch)
1057// Ensure the phi node's incoming blocks are the loop preheader and latch. 1058if (Phi->getBasicBlockIndex(Preheader) < 0 ||
1059 Phi->getBasicBlockIndex(Latch) < 0)
1062// Get the previous value. The previous value comes from the latch edge while 1063// the initial value comes from the preheader edge. 1064auto *Previous = dyn_cast<Instruction>(Phi->getIncomingValueForBlock(Latch));
1066// If Previous is a phi in the header, go through incoming values from the 1067// latch until we find a non-phi value. Use this as the new Previous, all uses 1068// in the header will be dominated by the original phi, but need to be moved 1069// after the non-phi previous value. 1071while (
auto *PrevPhi = dyn_cast_or_null<PHINode>(Previous)) {
1072if (PrevPhi->getParent() != Phi->getParent())
1074if (!SeenPhis.
insert(PrevPhi).second)
1076 Previous = dyn_cast<Instruction>(PrevPhi->getIncomingValueForBlock(Latch));
1079if (!Previous || !TheLoop->
contains(Previous) || isa<PHINode>(Previous))
1082// Ensure every user of the phi node (recursively) is dominated by the 1083// previous value. The dominance requirement ensures the loop vectorizer will 1084// not need to vectorize the initial value prior to the first iteration of the 1086// TODO: Consider extending this sinking to handle memory instructions. 1091auto TryToPushSinkCandidate = [&](
Instruction *SinkCandidate) {
1092// Cyclic dependence. 1093if (Previous == SinkCandidate)
1096if (!Seen.
insert(SinkCandidate).second)
1099 SinkCandidate))
// We already are good w/o sinking. 1102if (SinkCandidate->getParent() != PhiBB ||
1103 SinkCandidate->mayHaveSideEffects() ||
1104 SinkCandidate->mayReadFromMemory() || SinkCandidate->isTerminator())
1107// If we reach a PHI node that is not dominated by Previous, we reached a 1108// header PHI. No need for sinking. 1109if (isa<PHINode>(SinkCandidate))
1112// Sink User tentatively and check its users 1118// Try to recursively sink instructions and their users after Previous. 1119while (!WorkList.
empty()) {
1122if (!TryToPushSinkCandidate(cast<Instruction>(
User)))
1133return Instruction::Add;
1135return Instruction::Mul;
1137return Instruction::Or;
1139return Instruction::And;
1141return Instruction::Xor;
1143return Instruction::FMul;
1146return Instruction::FAdd;
1153return Instruction::ICmp;
1160return Instruction::FCmp;
1171// Search down from the Phi to the LoopExitInstr, looking for instructions 1172// with a single user of the correct type for the reduction. 1174// Note that we check that the type of the operand is correct for each item in 1175// the chain, including the last (the loop exit value). This can come up from 1176// sub, which would otherwise be treated as an add reduction. MinMax also need 1177// to check for a pair of icmp/select, for which we use getNextInstruction and 1178// isCorrectOpcode functions to step the right number of instruction, and 1179// check the icmp/select pair. 1180// FIXME: We also do not attempt to look through Select's yet, which might 1181// be part of the reduction chain, or attempt to looks through And's to find a 1182// smaller bitwidth. Subs are also currently not allowed (which are usually 1183// treated as part of a add reduction) as they are expected to generally be 1184// more expensive than out-of-loop reductions, and need to be costed more 1186unsigned ExpectedUses = 1;
1187if (RedOp == Instruction::ICmp || RedOp == Instruction::FCmp)
1193if (isa<PHINode>(UI))
1195if (RedOp == Instruction::ICmp || RedOp == Instruction::FCmp) {
1196// We are expecting a icmp/select pair, which we go to the next select 1197// instruction if we can. We already know that Cur has 2 uses. 1198if (isa<SelectInst>(UI))
1207if (RedOp == Instruction::ICmp || RedOp == Instruction::FCmp) {
1212// Recognize a call to the llvm.fmuladd intrinsic. 1216return Cur->getOpcode() == RedOp;
1219// Attempt to look through Phis which are part of the reduction chain 1220unsigned ExtraPhiUses = 0;
1222if (
auto ExitPhi = dyn_cast<PHINode>(LoopExitInstr)) {
1223if (ExitPhi->getNumIncomingValues() != 2)
1226Instruction *Inc0 = dyn_cast<Instruction>(ExitPhi->getIncomingValue(0));
1227Instruction *Inc1 = dyn_cast<Instruction>(ExitPhi->getIncomingValue(1));
1241// The loop exit instruction we check first (as a quick test) but add last. We 1242// check the opcode is correct (and dont allow them to be Subs) and that they 1243// have expected to have the expected number of uses. They will have one use 1244// from the phi and one from a LCSSA value, no matter the type. 1245if (!isCorrectOpcode(RdxInstr) || !LoopExitInstr->
hasNUses(2))
1248// Check that the Phi has one (or two for min/max) uses, plus an extra use 1249// for conditional reductions. 1250if (!Phi->hasNUses(ExpectedUses + ExtraPhiUses))
1255// Each other instruction in the chain should have the expected number of uses 1256// and be the correct opcode. 1257while (Cur != RdxInstr) {
1258if (!Cur || !isCorrectOpcode(Cur) || !Cur->
hasNUses(ExpectedUses))
1262 Cur = getNextInstruction(Cur);
1266return ReductionOperations;
1272 : StartValue(Start), IK(K), Step(Step), InductionBinOp(BOp) {
1273assert(IK != IK_NoInduction &&
"Not an induction");
1275// Start value type should match the induction kind and the value 1276// itself should not be null. 1277assert(StartValue &&
"StartValue is null");
1279"StartValue is not a pointer for pointer induction");
1281"StartValue is not an integer for integer induction");
1283// Check the Step Value. It should be non-zero integer value. 1284assert((!getConstIntStepValue() || !getConstIntStepValue()->
isZero()) &&
1285"Step value is zero");
1288"StepValue is not an integer");
1291"StepValue is not FP for FpInduction");
1292assert((IK != IK_FpInduction ||
1294 (InductionBinOp->getOpcode() == Instruction::FAdd ||
1295 InductionBinOp->getOpcode() == Instruction::FSub))) &&
1296"Binary opcode should be specified for FP induction");
1299for (
auto &Inst : *Casts) {
1300 RedundantCasts.push_back(Inst);
1306if (isa<SCEVConstant>(Step))
1307return dyn_cast<ConstantInt>(cast<SCEVConstant>(Step)->getValue());
1315// Here we only handle FP induction variables. 1316assert(Phi->getType()->isFloatingPointTy() &&
"Unexpected Phi type");
1318if (TheLoop->
getHeader() != Phi->getParent())
1321// The loop may have multiple entrances or multiple exits; we can analyze 1322// this phi if it has a unique entry value and a unique backedge value. 1323if (Phi->getNumIncomingValues() != 2)
1325Value *BEValue =
nullptr, *StartValue =
nullptr;
1326if (TheLoop->
contains(Phi->getIncomingBlock(0))) {
1327 BEValue = Phi->getIncomingValue(0);
1328 StartValue = Phi->getIncomingValue(1);
1331"Unexpected Phi node in the loop");
1332 BEValue = Phi->getIncomingValue(1);
1333 StartValue = Phi->getIncomingValue(0);
1340Value *Addend =
nullptr;
1341if (BOp->
getOpcode() == Instruction::FAdd) {
1346 }
elseif (BOp->
getOpcode() == Instruction::FSub)
1353// The addend should be loop invariant 1354if (
auto *
I = dyn_cast<Instruction>(Addend))
1358// FP Step has unknown SCEV 1364/// This function is called when we suspect that the update-chain of a phi node 1365/// (whose symbolic SCEV expression sin \p PhiScev) contains redundant casts, 1366/// that can be ignored. (This can happen when the PSCEV rewriter adds a runtime 1367/// predicate P under which the SCEV expression for the phi can be the 1368/// AddRecurrence \p AR; See createAddRecFromPHIWithCast). We want to find the 1369/// cast instructions that are involved in the update-chain of this induction. 1370/// A caller that adds the required runtime predicate can be free to drop these 1371/// cast instructions, and compute the phi using \p AR (instead of some scev 1372/// expression with casts). 1374/// For example, without a predicate the scev expression can take the following 1376/// (Ext ix (Trunc iy ( Start + i*Step ) to ix) to iy) 1378/// It corresponds to the following IR sequence: 1380/// %x = phi i64 [ 0, %ph ], [ %add, %for.body ] 1381/// %casted_phi = "ExtTrunc i64 %x" 1382/// %add = add i64 %casted_phi, %step 1384/// where %x is given in \p PN, 1385/// PSE.getSCEV(%x) is equal to PSE.getSCEV(%casted_phi) under a predicate, 1386/// and the IR sequence that "ExtTrunc i64 %x" represents can take one of 1387/// several forms, for example, such as: 1388/// ExtTrunc1: %casted_phi = and %x, 2^n-1 1390/// ExtTrunc2: %t = shl %x, m 1391/// %casted_phi = ashr %t, m 1393/// If we are able to find such sequence, we return the instructions 1394/// we found, namely %casted_phi and the instructions on its use-def chain up 1395/// to the phi (not including the phi). 1401assert(CastInsts.
empty() &&
"CastInsts is expected to be empty.");
1402auto *PN = cast<PHINode>(PhiScev->
getValue());
1403assert(PSE.
getSCEV(PN) == AR &&
"Unexpected phi node SCEV expression");
1406// Find any cast instructions that participate in the def-use chain of 1407// PhiScev in the loop. 1408// FORNOW/TODO: We currently expect the def-use chain to include only 1409// two-operand instructions, where one of the operands is an invariant. 1410// createAddRecFromPHIWithCasts() currently does not support anything more 1411// involved than that, so we keep the search simple. This can be 1412// extended/generalized as needed. 1414auto getDef = [&](
constValue *Val) ->
Value * {
1421if (L->isLoopInvariant(Op0))
1423elseif (L->isLoopInvariant(Op1))
1428// Look for the instruction that defines the induction via the 1433Value *Val = PN->getIncomingValueForBlock(Latch);
1437// Follow the def-use chain until the induction phi is reached. 1438// If on the way we encounter a Value that has the same SCEV Expr as the 1439// phi node, we can consider the instructions we visit from that point 1440// as part of the cast-sequence that can be ignored. 1441bool InCastSequence =
false;
1442auto *Inst = dyn_cast<Instruction>(Val);
1444// If we encountered a phi node other than PN, or if we left the loop, 1446if (!Inst || !L->contains(Inst)) {
1449auto *AddRec = dyn_cast<SCEVAddRecExpr>(PSE.
getSCEV(Val));
1451 InCastSequence =
true;
1452if (InCastSequence) {
1453// Only the last instruction in the cast sequence is expected to have 1454// uses outside the induction def-use chain. 1455if (!CastInsts.
empty())
1456if (!Inst->hasOneUse())
1463 Inst = dyn_cast<Instruction>(Val);
1466return InCastSequence;
1472Type *PhiTy = Phi->getType();
1474// Handle integer and pointer inductions variables. 1475// Now we handle also FP induction but not trying to make a 1476// recurrent expression from the PHI node in-place. 1486constauto *AR = dyn_cast<SCEVAddRecExpr>(PhiScev);
1488// We need this expression to be an AddRecExpr. 1497// Record any Cast instructions that participate in the induction update 1498constauto *SymbolicPhi = dyn_cast<SCEVUnknown>(PhiScev);
1499// If we started from an UnknownSCEV, and managed to build an addRecurrence 1500// only after enabling Assume with PSCEV, this means we may have encountered 1501// cast instructions that required adding a runtime check in order to 1502// guarantee the correctness of the AddRecurrence respresentation of the 1504if (PhiScev != AR && SymbolicPhi) {
1517Type *PhiTy = Phi->getType();
1518// isSCEVable returns true for integer and pointer types. 1522// Check that the PHI is consecutive. 1523constSCEV *PhiScev = Expr ? Expr : SE->
getSCEV(Phi);
1531if (AR->
getLoop() != TheLoop) {
1532// FIXME: We should treat this as a uniform. Unfortunately, we 1533// don't currently know how to handled uniform PHIs. 1535dbgs() <<
"LV: PHI is a recurrence with respect to an outer loop.\n");
1539// This function assumes that InductionPhi is called only on Phi nodes 1540// present inside loop headers. Check for the same, and throw an assert if 1541// the current Phi is not present inside the loop header. 1543 &&
"Invalid Phi node, not present in loop header");
1553// Calculate the pointer stride and check if it is consecutive. 1554// The stride may be a constant or a loop invariant integer value. 1555constSCEVConstant *ConstStep = dyn_cast<SCEVConstant>(Step);
1561 dyn_cast<BinaryOperator>(Phi->getIncomingValueForBlock(Latch));
1569// This allows induction variables w/non-constant steps. AMDGPU Register Bank Select
MachineBasicBlock MachineBasicBlock::iterator DebugLoc DL
static GCRegistry::Add< StatepointGC > D("statepoint-example", "an example strategy for statepoint")
static bool getCastsForInductionPHI(PredicatedScalarEvolution &PSE, const SCEVUnknown *PhiScev, const SCEVAddRecExpr *AR, SmallVectorImpl< Instruction * > &CastInsts)
This function is called when we suspect that the update-chain of a phi node (whose symbolic SCEV expr...
static void collectCastInstrs(Loop *TheLoop, Instruction *Exit, Type *RecurrenceType, SmallPtrSetImpl< Instruction * > &Casts, unsigned &MinWidthCastToRecurTy)
Collect cast instructions that can be ignored in the vectorizer's cost model, given a reduction exit ...
static bool checkOrderedReduction(RecurKind Kind, Instruction *ExactFPMathInst, Instruction *Exit, PHINode *Phi)
static Instruction * lookThroughAnd(PHINode *Phi, Type *&RT, SmallPtrSetImpl< Instruction * > &Visited, SmallPtrSetImpl< Instruction * > &CI)
Determines if Phi may have been type-promoted.
static std::pair< Type *, bool > computeRecurrenceType(Instruction *Exit, DemandedBits *DB, AssumptionCache *AC, DominatorTree *DT)
Compute the minimal bit width needed to represent a reduction whose exit instruction is given by Exit...
static bool isZero(Value *V, const DataLayout &DL, DominatorTree *DT, AssumptionCache *AC)
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
Class for arbitrary precision integers.
static APInt getSignedMinValue(unsigned numBits)
Gets minimum signed value of APInt for a specific bit width.
A cache of @llvm.assume calls within a function.
LLVM Basic Block Representation.
BinaryOps getOpcode() const
This class is the base class for the comparison instructions.
An abstraction over a floating-point predicate, and a pack of an integer predicate with samesign info...
This is the shared class of boolean and integer constants.
This class represents a range of values.
bool contains(const APInt &Val) const
Return true if the specified value is in the set.
static ConstantRange getNonEmpty(APInt Lower, APInt Upper)
Create non-empty constant range with the given bounds.
A parsed version of the target data layout string in and methods for querying it.
Concrete subclass of DominatorTreeBase that is used to compute a normal dominator tree.
bool dominates(const BasicBlock *BB, const Use &U) const
Return true if the (end of the) basic block BB dominates the use U.
Convenience struct for specifying and reasoning about fast-math flags.
bool noSignedZeros() const
void setNoSignedZeros(bool B=true)
void setNoNaNs(bool B=true)
static FastMathFlags getFast()
A struct for saving information about induction variables.
@ IK_FpInduction
Floating point induction variable.
@ IK_PtrInduction
Pointer induction var. Step = C.
@ IK_IntInduction
Integer induction variable. Step = C.
static bool isInductionPHI(PHINode *Phi, const Loop *L, ScalarEvolution *SE, InductionDescriptor &D, const SCEV *Expr=nullptr, SmallVectorImpl< Instruction * > *CastsToIgnore=nullptr)
Returns true if Phi is an induction in the loop L.
static bool isFPInductionPHI(PHINode *Phi, const Loop *L, ScalarEvolution *SE, InductionDescriptor &D)
Returns true if Phi is a floating point induction in the loop L.
InductionDescriptor()=default
Default constructor - creates an invalid induction.
ConstantInt * getConstIntStepValue() const
bool isCommutative() const LLVM_READONLY
Return true if the instruction is commutative:
FastMathFlags getFastMathFlags() const LLVM_READONLY
Convenience function for getting all the fast-math flags, which must be an operator which supports th...
static IntegerType * get(LLVMContext &C, unsigned NumBits)
This static method is the primary way of constructing an IntegerType.
bool contains(const LoopT *L) const
Return true if the specified loop is contained within in this loop.
BlockT * getLoopLatch() const
If there is a single latch block for this loop, return it.
BlockT * getHeader() const
BlockT * getLoopPreheader() const
If there is a preheader for this loop, return it.
Represents a single loop in the control flow graph.
bool isLoopInvariant(const Value *V) const
Return true if the specified value is loop invariant.
An interface layer with SCEV used to manage how we see SCEV expressions for values in the context of ...
ScalarEvolution * getSE() const
Returns the ScalarEvolution analysis used.
bool areAddRecsEqualWithPreds(const SCEVAddRecExpr *AR1, const SCEVAddRecExpr *AR2) const
Check if AR1 and AR2 are equal, while taking into account Equal predicates in Preds.
const SCEVAddRecExpr * getAsAddRec(Value *V)
Attempts to produce an AddRecExpr for V by adding additional SCEV predicates.
const SCEV * getSCEV(Value *V)
Returns the SCEV expression of V, in the context of the current SCEV predicate.
This POD struct holds information about a potential recurrence operation.
RecurKind getRecKind() const
Instruction * getPatternInst() const
bool isRecurrence() const
Instruction * getExactFPMathInst() const
The RecurrenceDescriptor is used to identify recurrences variables in a loop.
static bool isFPMinMaxRecurrenceKind(RecurKind Kind)
Returns true if the recurrence kind is a floating-point min/max kind.
static bool isFMulAddIntrinsic(Instruction *I)
Returns true if the instruction is a call to the llvm.fmuladd intrinsic.
static bool isFixedOrderRecurrence(PHINode *Phi, Loop *TheLoop, DominatorTree *DT)
Returns true if Phi is a fixed-order recurrence.
unsigned getOpcode() const
static bool hasMultipleUsesOf(Instruction *I, SmallPtrSetImpl< Instruction * > &Insts, unsigned MaxNumUses)
Returns true if instruction I has multiple uses in Insts.
static bool isReductionPHI(PHINode *Phi, Loop *TheLoop, RecurrenceDescriptor &RedDes, DemandedBits *DB=nullptr, AssumptionCache *AC=nullptr, DominatorTree *DT=nullptr, ScalarEvolution *SE=nullptr)
Returns true if Phi is a reduction in TheLoop.
static bool areAllUsesIn(Instruction *I, SmallPtrSetImpl< Instruction * > &Set)
Returns true if all uses of the instruction I is within the Set.
SmallVector< Instruction *, 4 > getReductionOpChain(PHINode *Phi, Loop *L) const
Attempts to find a chain of operations from Phi to LoopExitInst that can be treated as a set of reduc...
static bool isAnyOfRecurrenceKind(RecurKind Kind)
Returns true if the recurrence kind is of the form select(cmp(),x,y) where one of (x,...
static InstDesc isFindLastIVPattern(Loop *TheLoop, PHINode *OrigPhi, Instruction *I, ScalarEvolution &SE)
Returns a struct describing whether the instruction is either a Select(ICmp(A, B),...
static InstDesc isAnyOfPattern(Loop *Loop, PHINode *OrigPhi, Instruction *I, InstDesc &Prev)
Returns a struct describing whether the instruction is either a Select(ICmp(A, B),...
static bool isFindLastIVRecurrenceKind(RecurKind Kind)
Returns true if the recurrence kind is of the form select(cmp(),x,y) where one of (x,...
static InstDesc isConditionalRdxPattern(RecurKind Kind, Instruction *I)
Returns a struct describing if the instruction is a Select(FCmp(X, Y), (Z = X op PHINode),...
RecurKind getRecurrenceKind() const
StoreInst * IntermediateStore
Reductions may store temporary or final result to an invariant address.
static InstDesc isRecurrenceInstr(Loop *L, PHINode *Phi, Instruction *I, RecurKind Kind, InstDesc &Prev, FastMathFlags FuncFMF, ScalarEvolution *SE)
Returns a struct describing if the instruction 'I' can be a recurrence variable of type 'Kind' for a ...
static bool isFloatingPointRecurrenceKind(RecurKind Kind)
Returns true if the recurrence kind is a floating point kind.
static InstDesc isMinMaxPattern(Instruction *I, RecurKind Kind, const InstDesc &Prev)
Returns a struct describing if the instruction is a llvm.
static bool AddReductionVar(PHINode *Phi, RecurKind Kind, Loop *TheLoop, FastMathFlags FuncFMF, RecurrenceDescriptor &RedDes, DemandedBits *DB=nullptr, AssumptionCache *AC=nullptr, DominatorTree *DT=nullptr, ScalarEvolution *SE=nullptr)
Returns true if Phi is a reduction of type Kind and adds it to the RecurrenceDescriptor.
static bool isIntegerRecurrenceKind(RecurKind Kind)
Returns true if the recurrence kind is an integer kind.
static bool isIntMinMaxRecurrenceKind(RecurKind Kind)
Returns true if the recurrence kind is an integer min/max kind.
static bool isMinMaxRecurrenceKind(RecurKind Kind)
Returns true if the recurrence kind is any min/max kind.
This node represents a polynomial recurrence on the trip count of the specified loop.
const SCEV * getStepRecurrence(ScalarEvolution &SE) const
Constructs and returns the recurrence indicating how much this expression steps by.
const Loop * getLoop() const
This class represents a constant integer value.
This means that we are dealing with an entirely unknown SCEV value, and only represent it as its LLVM...
This class represents an analyzed expression in the program.
Type * getType() const
Return the LLVM type of this SCEV expression.
The main scalar evolution driver.
const SCEV * getSCEV(Value *V)
Return a SCEV expression for the full generality of the specified expression.
ConstantRange getSignedRange(const SCEV *S)
Determine the signed range for a particular SCEV.
bool isLoopInvariant(const SCEV *S, const Loop *L)
Return true if the value of the given SCEV is unchanging in the specified loop.
bool isKnownPositive(const SCEV *S)
Test if the given expression is known to be positive.
bool isSCEVable(Type *Ty) const
Test if values of the given type are analyzable within the SCEV framework.
const SCEV * getUnknown(Value *V)
This class represents the LLVM 'select' instruction.
A templated base class for SmallPtrSet which provides the typesafe interface that is common across al...
size_type count(ConstPtrType Ptr) const
count - Return 1 if the specified pointer is in the set, 0 otherwise.
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.
This class consists of common code factored out of the SmallVector class to reduce code duplication b...
void append(ItTy in_start, ItTy in_end)
Add the specified range to the end of the SmallVector.
void push_back(const T &Elt)
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
An instruction for storing to memory.
Value * getValueOperand()
Value * getPointerOperand()
The instances of the Type class are immutable: once they are created, they are never changed.
unsigned getIntegerBitWidth() const
bool isPointerTy() const
True if this is an instance of PointerType.
bool isFloatTy() const
Return true if this is 'float', a 32-bit IEEE fp type.
static IntegerType * getIntNTy(LLVMContext &C, unsigned N)
bool isHalfTy() const
Return true if this is 'half', a 16-bit IEEE fp type.
bool isDoubleTy() const
Return true if this is 'double', a 64-bit IEEE fp type.
bool isFloatingPointTy() const
Return true if this is one of the floating-point types.
bool isIntegerTy() const
True if this is an instance of IntegerType.
A Use represents the edge between a Value definition and its users.
Value * getOperand(unsigned i) const
LLVM Value Representation.
Type * getType() const
All values are typed, get the type of this value.
bool hasOneUse() const
Return true if there is exactly one use of this value.
iterator_range< user_iterator > users()
bool hasNUses(unsigned N) const
Return true if this Value has exactly N uses.
const ParentTy * getParent() const
#define llvm_unreachable(msg)
Marks that the current location is not supposed to be reachable.
BinaryOp_match< LHS, RHS, Instruction::And > m_And(const LHS &L, const RHS &R)
BinaryOp_match< LHS, RHS, Instruction::Add > m_Add(const LHS &L, const RHS &R)
BinaryOp_match< LHS, RHS, Instruction::FSub > m_FSub(const LHS &L, const RHS &R)
BinaryOp_match< LHS, RHS, Instruction::FMul > m_FMul(const LHS &L, const RHS &R)
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.
ThreeOps_match< Cond, LHS, RHS, Instruction::Select > m_Select(const Cond &C, const LHS &L, const RHS &R)
Matches SelectInst.
match_combine_or< MaxMin_match< FCmpInst, LHS, RHS, ofmin_pred_ty >, MaxMin_match< FCmpInst, LHS, RHS, ufmin_pred_ty > > m_OrdOrUnordFMin(const LHS &L, const RHS &R)
Match an 'ordered' or 'unordered' floating point minimum function.
MaxMin_match< ICmpInst, LHS, RHS, smin_pred_ty > m_SMin(const LHS &L, const RHS &R)
BinaryOp_match< LHS, RHS, Instruction::FAdd > m_FAdd(const LHS &L, const RHS &R)
BinaryOp_match< LHS, RHS, Instruction::Mul > m_Mul(const LHS &L, const RHS &R)
OneUse_match< T > m_OneUse(const T &SubPattern)
MaxMin_match< ICmpInst, LHS, RHS, umax_pred_ty > m_UMax(const LHS &L, const RHS &R)
class_match< CmpInst > m_Cmp()
Matches any compare instruction and ignore it.
match_combine_or< MaxMin_match< FCmpInst, LHS, RHS, ofmax_pred_ty >, MaxMin_match< FCmpInst, LHS, RHS, ufmax_pred_ty > > m_OrdOrUnordFMax(const LHS &L, const RHS &R)
Match an 'ordered' or 'unordered' floating point maximum function.
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::Sub > m_Sub(const LHS &L, const RHS &R)
MaxMin_match< ICmpInst, LHS, RHS, umin_pred_ty > m_UMin(const LHS &L, const RHS &R)
match_combine_or< LTy, RTy > m_CombineOr(const LTy &L, const RTy &R)
Combine two pattern matchers matching L || R.
This is an optimization pass for GlobalISel generic memory operations.
T bit_ceil(T Value)
Returns the smallest integral power of two no smaller than Value if Value is nonzero.
SelectPatternResult matchSelectPattern(Value *V, Value *&LHS, Value *&RHS, Instruction::CastOps *CastOp=nullptr, unsigned Depth=0)
Pattern match integer [SU]MIN, [SU]MAX and ABS idioms, returning the kind and providing the out param...
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
RecurKind
These are the kinds of recurrences that we support.
@ UMin
Unsigned integer min implemented in terms of select(cmp()).
@ IFindLastIV
FindLast reduction with select(icmp(),x,y) where one of (x,y) is increasing loop induction,...
@ FAnyOf
Any_of reduction with select(fcmp(),x,y) where one of (x,y) is loop invariant, and both x and y are i...
@ Or
Bitwise or logical OR of integers.
@ FMinimum
FP min with llvm.minimum semantics.
@ Mul
Product of integers.
@ Xor
Bitwise or logical XOR of integers.
@ FMax
FP max implemented in terms of select(cmp()).
@ FMaximum
FP max with llvm.maximum semantics.
@ FMulAdd
Sum of float products with llvm.fmuladd(a * b + sum).
@ SMax
Signed integer max implemented in terms of select(cmp()).
@ And
Bitwise or logical AND of integers.
@ FFindLastIV
FindLast reduction with select(fcmp(),x,y) where one of (x,y) is increasing loop induction,...
@ SMin
Signed integer min implemented in terms of select(cmp()).
@ FMin
FP min implemented in terms of select(cmp()).
@ IAnyOf
Any_of reduction with select(icmp(),x,y) where one of (x,y) is loop invariant, and both x and y are i...
@ UMax
Unsigned integer max implemented in terms of select(cmp()).
void computeKnownBits(const Value *V, KnownBits &Known, const DataLayout &DL, unsigned Depth=0, AssumptionCache *AC=nullptr, const Instruction *CxtI=nullptr, const DominatorTree *DT=nullptr, bool UseInstrInfo=true)
Determine which bits of V are known to be either zero or one and return them in the KnownZero/KnownOn...
bool is_contained(R &&Range, const E &Element)
Returns true if Element is found in Range.
unsigned ComputeNumSignBits(const Value *Op, const DataLayout &DL, unsigned Depth=0, AssumptionCache *AC=nullptr, const Instruction *CxtI=nullptr, const DominatorTree *DT=nullptr, bool UseInstrInfo=true)
Return the number of times the sign bit of the register is replicated into the other bits.
static bool isMinOrMax(SelectPatternFlavor SPF)
When implementing this min/max pattern as fcmp; select, does the fcmp have to be ordered?
