Index: include/llvm/Transforms/Utils/LoopUtils.h =================================================================== --- include/llvm/Transforms/Utils/LoopUtils.h +++ include/llvm/Transforms/Utils/LoopUtils.h @@ -36,6 +36,13 @@ class SCEV; class TargetLibraryInfo; +/// \enum for query result +enum QueryResult { + False = 0, + True, + Maybe +}; + /// \brief Captures loop safety information. /// It keep information for loop & its header may throw exception. struct LoopSafetyInfo { @@ -71,6 +78,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 +98,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 +148,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 +161,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 +185,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 + /// 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 QueryResult 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 +209,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 +284,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) != True; }); } @@ -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) == True) 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,55 @@ 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 +437,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 +475,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 +501,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()) @@ -447,13 +530,18 @@ case Instruction::FSub: case Instruction::FAdd: return InstDesc(Kind == RK_FloatAdd, I, UAI); + case Instruction::Select: + if (Kind == RK_IntegerMinMaxIdx) { + // We have a minmax index candidate + if (isMinMaxIndexCandidate(SE, dyn_cast(I))) + return InstDesc(true, I); + } case Instruction::FCmp: case Instruction::ICmp: - case Instruction::Select: if (Kind != RK_IntegerMinMax && (!HasFunNoNaNAttr || Kind != RK_FloatMinMax)) return InstDesc(false, I); - return isMinMaxSelectCmpPattern(I, Prev); + return isMinMaxSelectCmpPattern(SE, I, Prev); } } @@ -470,53 +558,58 @@ return false; } -bool RecurrenceDescriptor::isReductionPHI(PHINode *Phi, Loop *TheLoop, - RecurrenceDescriptor &RedDes) { +QueryResult 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; + 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; + 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; + 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; + 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; + 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; + return True; + } + if (AddReductionVar(SE, Phi, RK_IntegerMinMaxIdx, TheLoop, HasFunNoNaNAttr, + RedDes)) { + DEBUG(dbgs() << "Suspect a MINMAX INDEX reduction PHI." << *Phi << "\n"); + return Maybe; //TODO: FIX } - if (AddReductionVar(Phi, RK_FloatMult, TheLoop, HasFunNoNaNAttr, RedDes)) { + if (AddReductionVar(SE, Phi, RK_FloatMult, TheLoop, HasFunNoNaNAttr, RedDes)) { DEBUG(dbgs() << "Found an FMult reduction PHI." << *Phi << "\n"); - return true; + 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; + 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; + return True; } // Not a reduction of known type. - return false; + return False; } bool RecurrenceDescriptor::isFirstOrderRecurrence(PHINode *Phi, Loop *TheLoop, 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; @@ -1396,6 +1401,10 @@ /// Returns True if Phi is a first-order recurrence in this loop. bool isFirstOrderRecurrence(const PHINode *Phi); + /// Returns True if it succeded to identify all the given list as Reductions + /// and add them to the Reduction list + bool handleSecondOrderReductions(VerificationList& ExtraVerificationRequired); + /// Return true if the block BB needs to be predicated in order for the loop /// to be vectorized. bool blockNeedsPredication(BasicBlock *BB); @@ -4832,7 +4841,51 @@ return; } +bool LoopVectorizationLegality::handleSecondOrderReductions( + VerificationList& ExtraVerificationRequired) { + unsigned identifiedItems = 0; + // Move over all the items in the verification list and check if each item can be considered + // a Reduction (relying on the Reduction List) + for(VerificationList::iterator it = ExtraVerificationRequired.begin(); + it != ExtraVerificationRequired.end(); it++) { + // Extract pair elements + 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 = dyn_cast(RedDes.getLoopExitInstr()); + if (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 (auto reduction_it : Reductions) { + 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; + identifiedItems++; + break; + } + } + } + } + } + // If we did not identify all the listed items report an error + if (identifiedItems != ExtraVerificationRequired.size()) { + // Unknown type found halt + DEBUG(dbgs() << "LV: Extra verification required of unsupported kind.\n"); + return false; + } + // We have identified all the listed items + return true; +} + bool LoopVectorizationLegality::canVectorizeInstrs() { + VerificationList ExtraVerificationRequired; BasicBlock *Header = TheLoop->getHeader(); // Look for the attribute signaling the absence of NaNs. @@ -4883,7 +4936,14 @@ } RecurrenceDescriptor RedDes; - if (RecurrenceDescriptor::isReductionPHI(Phi, TheLoop, RedDes)) { + if (RecurrenceDescriptor::isReductionPHI(PSE.getSE(), Phi, TheLoop, RedDes) != False) { + // 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 +4976,12 @@ return false; } // end of PHI handling + // We have Reductions that need extra verfication phase (depends on other + // reductions results) + if (!ExtraVerificationRequired.empty() && + !handleSecondOrderReductions(ExtraVerificationRequired)) + return false; + // We handle calls that: // * Are debug info intrinsics. // * Have a mapping to an IR intrinsic. Index: test/Transforms/LoopVectorize/minmax_index_identification.ll =================================================================== --- /dev/null +++ test/Transforms/LoopVectorize/minmax_index_identification.ll @@ -0,0 +1,72 @@ +;RUN: opt < %s -loop-vectorize -force-vector-interleave=1 -force-vector-width=4 -debug -S 2>&1 >/dev/null | FileCheck %s + +; ModuleID = 'tmp.c' +source_filename = "tmp.c" +target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128" +target triple = "x86_64-unknown-linux-gnu" + +; Function Attrs: norecurse nounwind readonly uwtable +define i32 @max_idx_before(i32* nocapture readonly %arr, i32 %N) local_unnamed_addr { +entry: + %cmp14 = icmp sgt i32 %N, 0 + br i1 %cmp14, label %for.body.preheader, label %for.cond.cleanup + +for.body.preheader: ; preds = %entry + %0 = load i32, i32* %arr, align 4 + br label %for.body + +for.cond.cleanup: ; preds = %for.body, %entry + %idx.0.lcssa = phi i32 [ 0, %entry ], [ %i.0.idx.0, %for.body ] + ret i32 %idx.0.lcssa + +for.body: ; preds = %for.body, %for.body.preheader +; CHECK-LABEL: max_idx_before +; CHECK: LV: Found a minmax index PHI: %idx.016 +; CHECK: Depends On: %max.015 + %indvars.iv = phi i64 [ 0, %for.body.preheader ], [ %indvars.iv.next, %for.body ] + %idx.016 = phi i32 [ 0, %for.body.preheader ], [ %i.0.idx.0, %for.body ] + %max.015 = phi i32 [ %0, %for.body.preheader ], [ %.max.0, %for.body ] + %arrayidx1 = getelementptr inbounds i32, i32* %arr, i64 %indvars.iv + %1 = load i32, i32* %arrayidx1, align 4 + %cmp2 = icmp slt i32 %max.015, %1 + %.max.0 = select i1 %cmp2, i32 %1, i32 %max.015 + %2 = trunc i64 %indvars.iv to i32 + %i.0.idx.0 = select i1 %cmp2, i32 %2, i32 %idx.016 + %indvars.iv.next = add nuw nsw i64 %indvars.iv, 1 + %lftr.wideiv = trunc i64 %indvars.iv.next to i32 + %exitcond = icmp eq i32 %lftr.wideiv, %N + br i1 %exitcond, label %for.cond.cleanup, label %for.body +} + +define i32 @max_idx_after(i32* nocapture readonly %arr, i32 %N) local_unnamed_addr { +entry: + %cmp14 = icmp sgt i32 %N, 0 + br i1 %cmp14, label %for.body.preheader, label %for.cond.cleanup + +for.body.preheader: ; preds = %entry + %0 = load i32, i32* %arr, align 4 + br label %for.body + +for.cond.cleanup: ; preds = %for.body, %entry + %idx.0.lcssa = phi i32 [ 0, %entry ], [ %i.0.idx.0, %for.body ] + ret i32 %idx.0.lcssa + +for.body: ; preds = %for.body, %for.body.preheader +; CHECK-LABEL: max_idx_after +; CHECK: LV: Found a minmax index PHI: %idx.016 +; CHECK: Depends On: %max.015 + %indvars.iv = phi i64 [ 0, %for.body.preheader ], [ %indvars.iv.next, %for.body ] + %max.015 = phi i32 [ %0, %for.body.preheader ], [ %.max.0, %for.body ] + %idx.016 = phi i32 [ 0, %for.body.preheader ], [ %i.0.idx.0, %for.body ] + %arrayidx1 = getelementptr inbounds i32, i32* %arr, i64 %indvars.iv + %1 = load i32, i32* %arrayidx1, align 4 + %cmp2 = icmp slt i32 %max.015, %1 + %.max.0 = select i1 %cmp2, i32 %1, i32 %max.015 + %2 = trunc i64 %indvars.iv to i32 + %i.0.idx.0 = select i1 %cmp2, i32 %2, i32 %idx.016 + %indvars.iv.next = add nuw nsw i64 %indvars.iv, 1 + %lftr.wideiv = trunc i64 %indvars.iv.next to i32 + %exitcond = icmp eq i32 %lftr.wideiv, %N + br i1 %exitcond, label %for.cond.cleanup, label %for.body +} +