Index: include/llvm/Transforms/Utils/LoopUtils.h =================================================================== --- include/llvm/Transforms/Utils/LoopUtils.h +++ include/llvm/Transforms/Utils/LoopUtils.h @@ -71,6 +71,7 @@ RK_IntegerAnd, ///< Bitwise or logical AND of numbers. RK_IntegerXor, ///< Bitwise or logical XOR of numbers. RK_IntegerMinMax, ///< Min/max implemented in terms of select(cmp()). + RK_IntegerMinMaxIdx,///< Min/max index implemented in terms of select(cmp(),idx). RK_FloatAdd, ///< Sum of floats. RK_FloatMult, ///< Product of floats. RK_FloatMinMax ///< Min/max implemented in terms of select(cmp()). @@ -90,13 +91,14 @@ RecurrenceDescriptor() : StartValue(nullptr), LoopExitInstr(nullptr), Kind(RK_NoRecurrence), MinMaxKind(MRK_Invalid), UnsafeAlgebraInst(nullptr), - RecurrenceType(nullptr), IsSigned(false) {} + RecurrenceType(nullptr), IsSigned(false), CmpInstr(nullptr) {} RecurrenceDescriptor(Value *Start, Instruction *Exit, RecurrenceKind K, MinMaxRecurrenceKind MK, Instruction *UAI, Type *RT, bool Signed, SmallPtrSetImpl &CI) : StartValue(Start), LoopExitInstr(Exit), Kind(K), MinMaxKind(MK), - UnsafeAlgebraInst(UAI), RecurrenceType(RT), IsSigned(Signed) { + UnsafeAlgebraInst(UAI), RecurrenceType(RT), IsSigned(Signed), + CmpInstr(nullptr) { CastInsts.insert(CI.begin(), CI.end()); } @@ -139,7 +141,7 @@ /// select(icmp()) this function advances the instruction pointer 'I' from the /// compare instruction to the select instruction and stores this pointer in /// 'PatternLastInst' member of the returned struct. - static InstDesc isRecurrenceInstr(Instruction *I, RecurrenceKind Kind, + static InstDesc isRecurrenceInstr(ScalarEvolution *SE, Instruction *I, RecurrenceKind Kind, InstDesc &Prev, bool HasFunNoNaNAttr); /// Returns true if instruction I has multiple uses in Insts @@ -152,7 +154,16 @@ /// Returns a struct describing if the instruction if the instruction is a /// Select(ICmp(X, Y), X, Y) instruction pattern corresponding to a min(X, Y) /// or max(X, Y). - static InstDesc isMinMaxSelectCmpPattern(Instruction *I, InstDesc &Prev); + static InstDesc isMinMaxSelectCmpPattern(ScalarEvolution *SE, Instruction *I, + InstDesc &Prev); + + /// Checks if the given Operands matches MinMax Index Pattern + static bool isMinMaxIndexOperands(ScalarEvolution *SE, Value *InductionCandidate, + Value *OldValueCandidate, Value *Result); + + /// Returns true if the given select instruction matches a select of index + /// e.g. select A, B; while one of A/B is a reduction and other one is phi + static bool isMinMaxIndexCandidate(ScalarEvolution *SE, SelectInst *SI); /// Returns identity corresponding to the RecurrenceKind. static Constant *getRecurrenceIdentity(RecurrenceKind K, Type *Tp); @@ -167,14 +178,14 @@ /// Returns true if Phi is a reduction of type Kind and adds it to the /// RecurrenceDescriptor. - static bool AddReductionVar(PHINode *Phi, RecurrenceKind Kind, Loop *TheLoop, - bool HasFunNoNaNAttr, + static bool AddReductionVar(ScalarEvolution *SE, PHINode *Phi, RecurrenceKind Kind, + Loop *TheLoop, bool HasFunNoNaNAttr, RecurrenceDescriptor &RedDes); /// Returns true if Phi is a reduction in TheLoop. The RecurrenceDescriptor is /// returned in RedDes. - static bool isReductionPHI(PHINode *Phi, Loop *TheLoop, - RecurrenceDescriptor &RedDes); + static bool isReductionPHI(ScalarEvolution *SE, PHINode *Phi, + Loop *TheLoop, RecurrenceDescriptor &RedDes); /// Returns true if Phi is a first-order recurrence. A first-order recurrence /// is a non-reduction recurrence relation in which the value of the @@ -191,6 +202,18 @@ Instruction *getLoopExitInstr() { return LoopExitInstr; } + void setCmpInstr(Instruction *Instr) { + assert(((Kind == RK_IntegerMinMax) || (Kind == RK_FloatMinMax)) && + "Should be MinMax Recurrence"); + CmpInstr = Instr; + } + + Instruction* getCmpInstr() { + assert(((Kind == RK_IntegerMinMax) || (Kind == RK_FloatMinMax)) && + "Should be MinMax Recurrence"); + return CmpInstr; + } + /// Returns true if the recurrence has unsafe algebra which requires a relaxed /// floating-point model. bool hasUnsafeAlgebra() { return UnsafeAlgebraInst != nullptr; } @@ -254,6 +277,9 @@ bool IsSigned; // Instructions used for type-promoting the recurrence. SmallPtrSet CastInsts; + // In case of minmax kind we can point to the cmp instruction + // used in case if cmp is shared between minmax and minmax index + Instruction *CmpInstr; }; /// A struct for saving information about induction variables. Index: lib/Transforms/Scalar/LoopInterchange.cpp =================================================================== --- lib/Transforms/Scalar/LoopInterchange.cpp +++ lib/Transforms/Scalar/LoopInterchange.cpp @@ -602,7 +602,7 @@ return !std::any_of(Ins->user_begin(), Ins->user_end(), [=](User *U) -> bool { PHINode *UserIns = dyn_cast(U); RecurrenceDescriptor RD; - return !UserIns || !RecurrenceDescriptor::isReductionPHI(UserIns, L, RD); + return !UserIns || !RecurrenceDescriptor::isReductionPHI(SE, UserIns, L, RD); }); } @@ -705,7 +705,7 @@ PHINode *PHI = cast(I); if (InductionDescriptor::isInductionPHI(PHI, SE, ID)) Inductions.push_back(PHI); - else if (RecurrenceDescriptor::isReductionPHI(PHI, L, RD)) + else if (RecurrenceDescriptor::isReductionPHI(SE, PHI, L, RD)) Reductions.push_back(PHI); else { DEBUG( Index: lib/Transforms/Utils/LoopUtils.cpp =================================================================== --- lib/Transforms/Utils/LoopUtils.cpp +++ lib/Transforms/Utils/LoopUtils.cpp @@ -51,6 +51,7 @@ case RK_IntegerAnd: case RK_IntegerXor: case RK_IntegerMinMax: + case RK_IntegerMinMaxIdx: return true; } return false; @@ -159,8 +160,9 @@ return true; } -bool RecurrenceDescriptor::AddReductionVar(PHINode *Phi, RecurrenceKind Kind, - Loop *TheLoop, bool HasFunNoNaNAttr, +bool RecurrenceDescriptor::AddReductionVar(ScalarEvolution *SE, PHINode *Phi, + RecurrenceKind Kind, Loop *TheLoop, + bool HasFunNoNaNAttr, RecurrenceDescriptor &RedDes) { if (Phi->getNumIncomingValues() != 2) return false; @@ -187,6 +189,12 @@ // must include the original PHI. bool FoundStartPHI = false; + // Turns to true if we found minmax index candidate in minmax pattern, in this + // case minmax value may or may not have an external usage (ExitInstruction) + // because it's already used in minmax index calculation + bool MinMaxIndexUseFound = false; + Instruction *MinMaxSharedCmpInstr = nullptr; + // To recognize min/max patterns formed by a icmp select sequence, we store // the number of instruction we saw from the recognized min/max pattern, // to make sure we only see exactly the two instructions. @@ -261,7 +269,7 @@ // the starting value (the Phi or an AND instruction if the Phi has been // type-promoted). if (Cur != Start) { - ReduxDesc = isRecurrenceInstr(Cur, Kind, ReduxDesc, HasFunNoNaNAttr); + ReduxDesc = isRecurrenceInstr(SE, Cur, Kind, ReduxDesc, HasFunNoNaNAttr); if (!ReduxDesc.isRecurrence()) return false; } @@ -292,6 +300,15 @@ for (User *U : Cur->users()) { Instruction *UI = cast(U); + // Skip min-max index select (will be checked later with the relevant Phi) + if((Kind == RK_IntegerMinMax || Kind == RK_FloatMinMax) && isa(UI) + && (isa(Cur) || isa(Cur)) + && isMinMaxIndexCandidate(SE, dyn_cast(UI))) { + MinMaxIndexUseFound = true; + MinMaxSharedCmpInstr = dyn_cast(UI->getOperand(0)); + continue; + } + // Check if we found the exit user. BasicBlock *Parent = UI->getParent(); if (!TheLoop->contains(Parent)) { @@ -324,7 +341,7 @@ } else if (!isa(UI) && ((!isa(UI) && !isa(UI) && !isa(UI)) || - !isMinMaxSelectCmpPattern(UI, IgnoredVal).isRecurrence())) + !isMinMaxSelectCmpPattern(SE, UI, IgnoredVal).isRecurrence())) return false; // Remember that we completed the cycle. @@ -341,7 +358,7 @@ NumCmpSelectPatternInst != 2) return false; - if (!FoundStartPHI || !FoundReduxOp || !ExitInstruction) + if (!FoundStartPHI || !FoundReduxOp || (!ExitInstruction && !MinMaxIndexUseFound)) return false; // If we think Phi may have been type-promoted, we also need to ensure that @@ -362,15 +379,56 @@ RecurrenceDescriptor RD( RdxStart, ExitInstruction, Kind, ReduxDesc.getMinMaxKind(), ReduxDesc.getUnsafeAlgebraInst(), RecurrenceType, IsSigned, CastInsts); - RedDes = RD; + // in case of minmax with a suspect of minmax index candidate save the shared + // cmp instruction for a later checks + if (((RD.getRecurrenceKind() == RK_IntegerMinMax) || + (RD.getRecurrenceKind() == RK_FloatMinMax)) && MinMaxIndexUseFound ) { + if (MinMaxSharedCmpInstr) { + RD.setCmpInstr(MinMaxSharedCmpInstr); + } + } + + RedDes = RD; return true; } +bool RecurrenceDescriptor::isMinMaxIndexOperands(ScalarEvolution *SE, Value *InductionCandidate, + Value *OldValueCandidate, Value *Result) { + if(isa(OldValueCandidate)) { + PHINode* Phi = dyn_cast(OldValueCandidate); + // first check the result is incoming value for that phi + bool found = false; + for(unsigned i = 0; i < Phi->getNumIncomingValues(); ++i) { + if(Phi->getIncomingValue(i) == Result) found = true; + } + // result is not incoming value for that phi + if (!found) return false; + + // Need to check the InductionCandidate + // Currently we support induction with step 1 + const SCEV* MayInduction = SE->getSCEV(InductionCandidate); + if(const SCEVAddRecExpr *AR = dyn_cast(MayInduction)) { + const SCEV *Step = AR->getStepRecurrence(*SE); + return Step->isOne(); + } + return false; + } + return false; +} + +bool RecurrenceDescriptor::isMinMaxIndexCandidate(ScalarEvolution *SE, SelectInst *SI) { + assert(SI && "given null select instr"); + + return isMinMaxIndexOperands(SE, SI->getTrueValue(), SI->getFalseValue(), SI) || + isMinMaxIndexOperands(SE, SI->getFalseValue(), SI->getTrueValue(), SI); +} + /// Returns true if the instruction is a Select(ICmp(X, Y), X, Y) instruction /// pattern corresponding to a min(X, Y) or max(X, Y). RecurrenceDescriptor::InstDesc -RecurrenceDescriptor::isMinMaxSelectCmpPattern(Instruction *I, InstDesc &Prev) { +RecurrenceDescriptor::isMinMaxSelectCmpPattern(ScalarEvolution *SE, Instruction *I, + InstDesc &Prev) { assert((isa(I) || isa(I) || isa(I)) && "Expect a select instruction"); @@ -380,6 +438,33 @@ // We must handle the select(cmp()) as a single instruction. Advance to the // select. if ((Cmp = dyn_cast(I)) || (Cmp = dyn_cast(I))) { + // we allow cmp to have more than one use only if it may be minmax index + // reduction type e.g.: + // %a = cmp CC, %X, %Y + // user1: %b = select %a, %X, %Y ; for minmax value + // user2: %c = select %a, OldIndex, CurIndex ; for minmax index + if (Cmp->getNumUses() == 2) { + // minmax index user should be select between itself(Old) and induction + // minmax value user can be different (min\max value) + SelectInst* Candidate = nullptr; + for (User *U : Cmp->users()) { + SelectInst *SI = dyn_cast(U); + if(!SI) + return InstDesc(false, I); + + if(!isMinMaxIndexCandidate(SE, SI)) { + // If we already have a minmax value candidate return false + if(Candidate) return InstDesc(false, I); + // In case we still dont have a minmax value candidate then mark this select + Candidate = SI; + } + } + // If we dont have minmax value candidate return false + if(!Candidate) + return InstDesc(false, I); + return InstDesc(Candidate, Prev.getMinMaxKind()); + } + // otherwise if (!Cmp->hasOneUse() || !(Select = dyn_cast(*I->user_begin()))) return InstDesc(false, I); return InstDesc(Select, Prev.getMinMaxKind()); @@ -391,8 +476,6 @@ if (!(Cmp = dyn_cast(I->getOperand(0))) && !(Cmp = dyn_cast(I->getOperand(0)))) return InstDesc(false, I); - if (!Cmp->hasOneUse()) - return InstDesc(false, I); Value *CmpLeft; Value *CmpRight; @@ -419,8 +502,9 @@ } RecurrenceDescriptor::InstDesc -RecurrenceDescriptor::isRecurrenceInstr(Instruction *I, RecurrenceKind Kind, - InstDesc &Prev, bool HasFunNoNaNAttr) { +RecurrenceDescriptor::isRecurrenceInstr(ScalarEvolution *SE, Instruction *I, + RecurrenceKind Kind, InstDesc &Prev, + bool HasFunNoNaNAttr) { bool FP = I->getType()->isFloatingPointTy(); Instruction *UAI = Prev.getUnsafeAlgebraInst(); if (!UAI && FP && !I->hasUnsafeAlgebra()) @@ -450,10 +534,17 @@ case Instruction::FCmp: case Instruction::ICmp: case Instruction::Select: + if (I->getOpcode() == Instruction::Select && + Kind == RK_IntegerMinMaxIdx) { + // We have a minmax index candidate + if (isMinMaxIndexCandidate(SE, dyn_cast(I))) { + return InstDesc(true, I); + } + } if (Kind != RK_IntegerMinMax && (!HasFunNoNaNAttr || Kind != RK_FloatMinMax)) return InstDesc(false, I); - return isMinMaxSelectCmpPattern(I, Prev); + return isMinMaxSelectCmpPattern(SE, I, Prev); } } @@ -470,48 +561,53 @@ return false; } -bool RecurrenceDescriptor::isReductionPHI(PHINode *Phi, Loop *TheLoop, - RecurrenceDescriptor &RedDes) { +bool RecurrenceDescriptor::isReductionPHI(ScalarEvolution* SE, PHINode *Phi, + Loop *TheLoop, RecurrenceDescriptor &RedDes) { BasicBlock *Header = TheLoop->getHeader(); Function &F = *Header->getParent(); bool HasFunNoNaNAttr = F.getFnAttribute("no-nans-fp-math").getValueAsString() == "true"; - if (AddReductionVar(Phi, RK_IntegerAdd, TheLoop, HasFunNoNaNAttr, RedDes)) { + if (AddReductionVar(SE, Phi, RK_IntegerAdd, TheLoop, HasFunNoNaNAttr, RedDes)) { DEBUG(dbgs() << "Found an ADD reduction PHI." << *Phi << "\n"); return true; } - if (AddReductionVar(Phi, RK_IntegerMult, TheLoop, HasFunNoNaNAttr, RedDes)) { + if (AddReductionVar(SE, Phi, RK_IntegerMult, TheLoop, HasFunNoNaNAttr, RedDes)) { DEBUG(dbgs() << "Found a MUL reduction PHI." << *Phi << "\n"); return true; } - if (AddReductionVar(Phi, RK_IntegerOr, TheLoop, HasFunNoNaNAttr, RedDes)) { + if (AddReductionVar(SE, Phi, RK_IntegerOr, TheLoop, HasFunNoNaNAttr, RedDes)) { DEBUG(dbgs() << "Found an OR reduction PHI." << *Phi << "\n"); return true; } - if (AddReductionVar(Phi, RK_IntegerAnd, TheLoop, HasFunNoNaNAttr, RedDes)) { + if (AddReductionVar(SE, Phi, RK_IntegerAnd, TheLoop, HasFunNoNaNAttr, RedDes)) { DEBUG(dbgs() << "Found an AND reduction PHI." << *Phi << "\n"); return true; } - if (AddReductionVar(Phi, RK_IntegerXor, TheLoop, HasFunNoNaNAttr, RedDes)) { + if (AddReductionVar(SE, Phi, RK_IntegerXor, TheLoop, HasFunNoNaNAttr, RedDes)) { DEBUG(dbgs() << "Found a XOR reduction PHI." << *Phi << "\n"); return true; } - if (AddReductionVar(Phi, RK_IntegerMinMax, TheLoop, HasFunNoNaNAttr, + if (AddReductionVar(SE, Phi, RK_IntegerMinMax, TheLoop, HasFunNoNaNAttr, RedDes)) { DEBUG(dbgs() << "Found a MINMAX reduction PHI." << *Phi << "\n"); return true; } - if (AddReductionVar(Phi, RK_FloatMult, TheLoop, HasFunNoNaNAttr, RedDes)) { + if (AddReductionVar(SE, Phi, RK_IntegerMinMaxIdx, TheLoop, HasFunNoNaNAttr, + RedDes)) { + DEBUG(dbgs() << "Suspect a MINMAX INDEX reduction PHI." << *Phi << "\n"); + return true; //TODO: FIX + } + if (AddReductionVar(SE, Phi, RK_FloatMult, TheLoop, HasFunNoNaNAttr, RedDes)) { DEBUG(dbgs() << "Found an FMult reduction PHI." << *Phi << "\n"); return true; } - if (AddReductionVar(Phi, RK_FloatAdd, TheLoop, HasFunNoNaNAttr, RedDes)) { + if (AddReductionVar(SE, Phi, RK_FloatAdd, TheLoop, HasFunNoNaNAttr, RedDes)) { DEBUG(dbgs() << "Found an FAdd reduction PHI." << *Phi << "\n"); return true; } - if (AddReductionVar(Phi, RK_FloatMinMax, TheLoop, HasFunNoNaNAttr, RedDes)) { + if (AddReductionVar(SE, Phi, RK_FloatMinMax, TheLoop, HasFunNoNaNAttr, RedDes)) { DEBUG(dbgs() << "Found an float MINMAX reduction PHI." << *Phi << "\n"); return true; } Index: lib/Transforms/Vectorize/LoopVectorize.cpp =================================================================== --- lib/Transforms/Vectorize/LoopVectorize.cpp +++ lib/Transforms/Vectorize/LoopVectorize.cpp @@ -1363,6 +1363,11 @@ /// induction descriptor. typedef MapVector InductionList; + // VerificationList contains all the suspected complex reductions + // which need another extra verification phase after we move over all + // other reductions + typedef DenseMap VerificationList; + /// RecurrenceSet contains the phi nodes that are recurrences other than /// inductions and reductions. typedef SmallPtrSet RecurrenceSet; @@ -4833,6 +4838,7 @@ } bool LoopVectorizationLegality::canVectorizeInstrs() { + VerificationList ExtraVerificationRequired; BasicBlock *Header = TheLoop->getHeader(); // Look for the attribute signaling the absence of NaNs. @@ -4883,7 +4889,14 @@ } RecurrenceDescriptor RedDes; - if (RecurrenceDescriptor::isReductionPHI(Phi, TheLoop, RedDes)) { + if (RecurrenceDescriptor::isReductionPHI(PSE.getSE(), Phi, TheLoop, RedDes)) { + // in case of minmax index still we should make sure that the 2nd pair is minmax + // this extra verification will be done in a later phase after we move over all + // the Phi's + if (RedDes.getRecurrenceKind() == RecurrenceDescriptor::RK_IntegerMinMaxIdx) { + ExtraVerificationRequired[Phi] = RedDes; + continue; + } if (RedDes.hasUnsafeAlgebra()) Requirements->addUnsafeAlgebraInst(RedDes.getUnsafeAlgebraInst()); AllowedExit.insert(RedDes.getLoopExitInstr()); @@ -4916,6 +4929,49 @@ return false; } // end of PHI handling + // We have Reductions that need extra verfication phase (depends on other + // reductions results) + if (!ExtraVerificationRequired.empty()) { + for(VerificationList::iterator it = ExtraVerificationRequired.begin(); + it != ExtraVerificationRequired.end(); it++) { + assert(isa(it->first) && "corrupted verification table"); + PHINode *PhiMinMaxIdCandidate = it->first; + RecurrenceDescriptor RedDes = it->second; + // We currently handle MinMax Idx pattern which depends on MinMax pattern + if (RedDes.getRecurrenceKind() == RecurrenceDescriptor::RK_IntegerMinMaxIdx) { + Instruction *LoopExit = RedDes.getLoopExitInstr(); + if (LoopExit && + isa(LoopExit) && + (isa(LoopExit->getOperand(0)) || isa(LoopExit->getOperand(0)))) { + Instruction *CmpInstr = dyn_cast(LoopExit->getOperand(0)); + // Move over all the reductions we have found and see if the suspected Cmp + // is used in min max pattern if yes then we have found a minmax index pattern + for (ReductionList::iterator reduction_it = Reductions.begin(); + reduction_it != Reductions.end(); + reduction_it++) { + RecurrenceDescriptor Des = reduction_it->second; + if (((Des.getRecurrenceKind() == RecurrenceDescriptor::RK_IntegerMinMax) || + (Des.getRecurrenceKind() == RecurrenceDescriptor::RK_FloatMinMax)) && + Des.getCmpInstr() == CmpInstr) { + DEBUG(dbgs() << "LV: Found a minmax index PHI: " << *PhiMinMaxIdCandidate + << "\nDepends On: " << *(reduction_it->first) << "\n"); + Reductions[PhiMinMaxIdCandidate] = RedDes; + break; + } + } + } + } + else { + // Unknown type found halt + DEBUG(dbgs() << "LV: Extra verification required of unsupported kind.\n"); + return false; + } + } + // Currently we dont handle minmax id pattern halt + DEBUG(dbgs() << "LV: Extra verfication required.\n"); + return false; + } + // We handle calls that: // * Are debug info intrinsics. // * Have a mapping to an IR intrinsic.