From b02b0ad8c78eab94b2c24333c5c378ffe90ea309 Mon Sep 17 00:00:00 2001 From: Anna Thomas Date: Tue, 21 Aug 2018 14:40:27 +0000 Subject: [LV] Vectorize loops where non-phi instructions used outside loop Summary: Follow up change to rL339703, where we now vectorize loops with non-phi instructions used outside the loop. Note that the cyclic dependency identification occurs when identifying reduction/induction vars. We also need to identify that we do not allow users where the PSCEV information within and outside the loop are different. This was the fix added in rL307837 for PR33706. Reviewers: Ayal, mkuper, fhahn Subscribers: javed.absar, llvm-commits Differential Revision: https://reviews.llvm.org/D50778 llvm-svn: 340278 --- .../Vectorize/LoopVectorizationLegality.cpp | 24 ++++++++++++++++++++-- 1 file changed, 22 insertions(+), 2 deletions(-) (limited to 'llvm/lib/Transforms/Vectorize/LoopVectorizationLegality.cpp') diff --git a/llvm/lib/Transforms/Vectorize/LoopVectorizationLegality.cpp b/llvm/lib/Transforms/Vectorize/LoopVectorizationLegality.cpp index 49f8658ef45..f23347e9cf6 100644 --- a/llvm/lib/Transforms/Vectorize/LoopVectorizationLegality.cpp +++ b/llvm/lib/Transforms/Vectorize/LoopVectorizationLegality.cpp @@ -436,8 +436,6 @@ static bool hasOutsideLoopUser(const Loop *TheLoop, Instruction *Inst, SmallPtrSetImpl &AllowedExit) { // Reductions, Inductions and non-header phis are allowed to have exit users. All // other instructions must not have external users. - // TODO: Non-phi instructions can also be taught to have exit users, now that - // we know how to extract the last scalar element from the loop. if (!AllowedExit.count(Inst)) // Check that all of the users of the loop are inside the BB. for (User *U : Inst->users()) { @@ -626,6 +624,20 @@ bool LoopVectorizationLegality::canVectorizeInstrs() { continue; } + // TODO: Instead of recording the AllowedExit, it would be good to record the + // complementary set: NotAllowedExit. These include (but may not be + // limited to): + // 1. Reduction phis as they represent the one-before-last value, which + // is not available when vectorized + // 2. Induction phis and increment when SCEV predicates cannot be used + // outside the loop - see addInductionPhi + // 3. Non-Phis with outside uses when SCEV predicates cannot be used + // outside the loop - see call to hasOutsideLoopUser in the non-phi + // handling below + // 4. FirstOrderRecurrence phis that can possibly be handled by + // extraction. + // By recording these, we can then reason about ways to vectorize each + // of these NotAllowedExit. InductionDescriptor ID; if (InductionDescriptor::isInductionPHI(Phi, TheLoop, PSE, ID)) { addInductionPhi(Phi, ID, AllowedExit); @@ -718,6 +730,14 @@ bool LoopVectorizationLegality::canVectorizeInstrs() { // Reduction instructions are allowed to have exit users. // All other instructions must not have external users. if (hasOutsideLoopUser(TheLoop, &I, AllowedExit)) { + // We can safely vectorize loops where instructions within the loop are + // used outside the loop only if the SCEV predicates within the loop is + // same as outside the loop. Allowing the exit means reusing the SCEV + // outside the loop. + if (PSE.getUnionPredicate().isAlwaysTrue()) { + AllowedExit.insert(&I); + continue; + } ORE->emit(createMissedAnalysis("ValueUsedOutsideLoop", &I) << "value cannot be used outside the loop"); return false; -- cgit v1.2.3