[LV] Emitting SCEV checks with OptForSize

[SjoerdMeijer]

Summary

This is addressing PR43371. When optimizing for size, and SCEV runtime checks
need to be emitted to check overflow behaviour, the loop vectorizer can run in this
assert:

  
LoopVectorize.cpp:2699: void llvm::InnerLoopVectorizer::emitSCEVChecks(
llvm::Loop *, llvm::BasicBlock *): Assertion `!BB->getParent()->hasOptSize()
&& "Cannot SCEV check stride or overflow when optimizing for size"'

SCEV should not generate predicates while optimising for size, because
code will be generated for predicates, such as these SCEV overflow runtime
checks.

[Ayal]

At this point, PSE.getUnionPredicate().getPredicates() returns 0

Can you track where/when the predicate is generated and added to PSE?

The original bailout in LoopVectorizationLegality::canVectorize() checking if (PSE.getUnionPredicate().getComplexity() > SCEVThreshold) could potentially be extended - essentially zeroing SCEVThreshold for hasOptSize, but this takes place *earlier* than runtimeChecksRequired() which is claimed to be too early, contrary to the following claim:

// Okay! We've done all the tests. If any have failed, return false. Otherwise
// we can vectorize, and at this point we don't have any other mem analysis
// which may limit our maximum vectorization factor, so just return true with
// no restrictions.

The latest bailout is probably LoopVectorizationCostModel::selectVectorizationFactor(), but it's better to bailout earlier.

BTW, a related opportunity is // FIXME: Avoid specializing for stride==1 instead of bailing out.

[SjoerdMeijer]

Thanks for all the pointers and info, that helped me getting back on track.
Hopefully things are actually as simple as the change in this patch (this passes check-all).

[Ayal]

llvm/lib/Transforms/Vectorize/LoopVectorize.cpp

6391

Better try to fix the issue at its core; isConsecutivePtr() should be conservative and avoid generating predicates under hasOptSize, by preventing getPtrStride() from doing so.
This may lead to successfully vectorizing the loop, albeit with a gather/scatter instead of a (speculative) vector load/store.

llvm/test/Transforms/LoopVectorize/pr43371-optsize-scevchecks.ll

6

Better try to augment existing optsize files with additional tests.

[SjoerdMeijer]

• modified SCEV so that it doesn't add Predicates when OptForSize is enabled. This has indeed the consequence that vectorisation will happen, it will scalarise the stores.
• moved the test case to an exisiting optsize file.

[SjoerdMeijer]

Apologies for the early ping and for the impatience! But I am just really keen on getting this fixed. :-)

[Ayal]

Changing PredicatedScalarEvolution::getAsAddRec() to consider hasOptSize sounds a bit strange to me; after all the transformation that created PSCEV should have considered this; adding @sanjoy for more thoughts on such a proposed SCEV change.

The earlier "fix at the core" thought was for LV to do something along these lines:

@@ -409,7 +409,9 @@ int LoopVectorizationLegality::isConsecutivePtr(Value *Ptr) {
   const ValueToValueMap &Strides =
       getSymbolicStrides() ? *getSymbolicStrides() : ValueToValueMap();
 
-  int Stride = getPtrStride(PSE, Ptr, TheLoop, Strides, true, false);
+  bool CanAddPredicates = !TheLoop->getHeader()->getParent()->hasOptSize();
+  int Stride =
+      getPtrStride(PSE, Ptr, TheLoop, Strides, CanAddPredicates, false);
   if (Stride == 1 || Stride == -1)
     return Stride;
   return 0;

and the related "BTW, a related opportunity is // FIXME: Avoid specializing for stride==1 instead of bailing out" was for LAI to do something along these lines:

@@ -2295,6 +2295,11 @@ void LoopAccessInfo::collectStridedAccess(Value *MemAccess) {
                        "versioning:");
   LLVM_DEBUG(dbgs() << "  Ptr: " << *Ptr << " Stride: " << *Stride << "\n");
 
+  if (TheLoop->getHeader()->getParent()->hasOptSize()) {
+    /* issue an LLVM_DEBUG message that versioning is avoided due to opt-for-size */
+    return;
+  }
+
   // Avoid adding the "Stride == 1" predicate when we know that
   // Stride >= Trip-Count. Such a predicate will effectively optimize a single
   // or zero iteration loop, as Trip-Count <= Stride == 1.

[SjoerdMeijer]

The earlier "fix at the core" thought was for LV to do something along these lines:

Okay, sorry for misunderstanding! The "core" for me was the place that produces predicates in the first place, which is happening by in PSE.getAsAddRec(Ptr) called by getPtrStride(). It was my understanding and line of thought that not producing them, return nullptr for getAsAddRec(), was the most clean and most minimal change, but I am not insisting at all of course! So thanks for your suggestions, I will prepare a patch based on this. If @sanjoy in the mean time does think this is an interesting change, then I could change again.

Thanks again for the help

[hsaito]

I agree with @Ayal about changing getAsAddRec for OptForSize. In general, it's better to not "Analyze" if we know we won't be using the result of analysis.

In this regard, I do not like pass managers running Analyses for a Transformation pass w/o first letting the Transformation pass inspect the incoming IR, but that's a totally different discussion and I don't have a solution for that problem. Is new pass manager any better there?

[sanjoy]

In D68082#1695125, @hsaito wrote:

I agree with @Ayal about changing getAsAddRec for OptForSize. In general, it's better to not "Analyze" if we know we won't be using the result of analysis.

+1

I vote against having SCEV depend on OptForSize.

In this regard, I do not like pass managers running Analyses for a Transformation pass w/o first letting the Transformation pass inspect the incoming IR, but that's a totally different discussion and I don't have a solution for that problem.

Maybe I'm misunderstanding, but SCEV is lazy so if a transform looks at the IR and decides not to ask SCEV for trip count or call getSCEV then SCEV will not do any actual work.

Is new pass manager any better there?

[hsaito]

>> In this regard, I do not like pass managers running Analyses for a Transformation pass w/o first letting the Transformation pass inspect the incoming IR, but that's a totally different discussion and I don't have a solution for that problem.

Maybe I'm misunderstanding, but SCEV is lazy so if a transform looks at the IR and decides not to ask SCEV for trip count or call getSCEV then SCEV will not do any actual work.

Not all analyses are lazy, right? For example, if all loops in the function have some structural issues that vectorizer doesn't like to work on, there aren't any reasons why we'd need to satisfy required analyses consumed only after that bail out point. Maybe, we just need to make many analyses lazy, i.e., not pass manager's problem.

[SjoerdMeijer]

Thanks for your comments and thoughts.

This adds/implements @Ayal 's suggestion.

[Ayal]

The other suggested fix in LoopAccessInfo::collectStridedAccess() indeed deserves a separate patch, being an optimization opportunity rather than preventing an assert -- it's stride predicate is added early enough to be caught by CM.computeMaxVF()'s bailout conditions and avoid assert, as scev4stride1() test in above X86/optsize.ll checks.

llvm/test/Transforms/LoopVectorize/X86/optsize.ll

7 ↗

(On Diff #223366)

Can one or both existing RUN's above be (re)used instead of adding a third?

201 ↗

(On Diff #223366)

run in an >> run into an

while >> due to

232 ↗

(On Diff #223366)

simplify the test: entry block can branch directly to the loop header block.

240 ↗

(On Diff #223366)

simplify the test: merge the two blocks of the loop into one.

[SjoerdMeijer]

Comments addressed:

• cleaned up the test case a bit.
• couldn't reuse an existing run-line, I guess because of -mcpu=skx, but a separate run line seems fine to me.

The other suggested fix in LoopAccessInfo::collectStridedAccess() indeed deserves a separate patch

Thanks for that suggestions, and I will address this separately. I have unfinished business in the vectorizer, and will add this to me my list of things to do next.

[Ayal]

In D68082#1696991, @SjoerdMeijer wrote:

Comments addressed:

• cleaned up the test case a bit.

Can be cleaned up a bit more, "header" block is still redundant.

• couldn't reuse an existing run-line, I guess because of -mcpu=skx, but a separate run line seems fine to me.

Interesting. Better to check instead of guess. This distinction means that

1. @pr43371() testcase belongs in test/Transforms/LoopVectorize/optsize.ll instead of test/Transforms/LoopVectorize/X86/optsize.ll
2. InterleavedAccessInfo::collectConstStrideAccesses() in Analysis/VectorUtils.cpp is responsible for creating the predicate under skx early enough to bailout (despite having no interleave groups eventually). Best teach it too to call getPtrStride() with Assume=!hasOptSize instead of 'true'. This is another performance opportunity rather than prevention of asserts.

The other suggested fix in LoopAccessInfo::collectStridedAccess() indeed deserves a separate patch

Thanks for that suggestions, and I will address this separately. I have unfinished business in the vectorizer, and will add this to me my list of things to do next.

[SjoerdMeijer]

Cheers, moved the test back to directory LoopVectorize where it once was instead of LoopVectorize\X86 (which was indeed a mistake, and then added the extra runline out of frustration as the skx core was unknown to me).

My TODO list has grown to fixing up:

1. InterleavedAccessInfo::collectConstStrideAccesses()
2. LoopAccessInfo::collectStridedAccess()

Will follow up on this shortly.

[Ayal]

This LGTM, with additional CHECK-NOT to the test, thanks!

llvm/test/Transforms/LoopVectorize/optsize.ll

100 ↗

(On Diff #224012)

Better also verify here that no SCEV predicates get generated, e.g., "CHECK-NOT: vector.scevcheck" as in pr39417-optsize-scevchecks.ll, or CHECK-NOT the predicates themselves as in pr34681.ll.

[SjoerdMeijer]

Many thanks again for reviewing. I will add the check-not before committing, and as I said, I will follow up soon to address the other improvements opportunities.

llvm/lib/Transforms/Vectorize/LoopVectorize.cpp

SCEVExpander Exp(*PSE.getSE(), Bypass->getModule()->getDataLayout(),
                    "scev.check");
   Value *SCEVCheck =
       Exp.expandCodeForPredicate(&PSE.getUnionPredicate(), BB->getTerminator());
 
   if (auto *C = dyn_cast<ConstantInt>(SCEVCheck))
     if (C->isZero())
       return;
 
-  assert(!BB->getParent()->hasOptSize() &&
-         "Cannot SCEV check stride or overflow when optimizing for size");
+  // FIXME: we should gracefully bail a lot earlier. The problem is that
+  // in runtimeChecksRequired(), where code-size increase is checked the first
+  // time, everything is different as e.g. unrolling is not applied yet. Thus,
+  // the SCEV information is different, and won't find any SCEV predicates,
+  // which we do find later, resulting in emitting SCEV runtime checks. As a
+  // workaround, we emit an optimization remark warning about the increase.
+  if (BB->getParent()->hasOptSize()) {
+    ORE->emit([&]() {
+      return OptimizationRemarkAnalysis(DEBUG_TYPE, "VectorizationCodeSize",
+                                        L->getStartLoc(), L->getHeader())
+             << "Optimizing for size, but overflow checks are emitted. Can "
+                "this be avoided by e.g. using a larger loop induction "
+                "variable type?";
+    });
+  }
 
   // Create a new block containing the stride check.
   BB->setName("vector.scevcheck");
   auto *NewBB = BB->splitBasicBlock(BB->getTerminator(), "vector.ph");
   // Update dominator tree immediately if the generated block is a
   // LoopBypassBlock because SCEV expansions to generate loop bypass
   // checks may query it before the current function is finished.
   DT->addNewBlock(NewBB, BB);
Optional<VectorizationFactor> LoopVectorizationPlanner::plan(unsigned UserVF) {
 
   unsigned MaxVF = MaybeMaxVF.getValue();
   assert(MaxVF != 0 && "MaxVF is zero.");
 
   for (unsigned VF = 1; VF <= MaxVF; VF *= 2) {
     // Collect Uniform and Scalar instructions after vectorization with VF.
     CM.collectUniformsAndScalars(VF);
 
     // Collect the instructions (and their associated costs) that will be more
     // profitable to scalarize.
     if (VF > 1)
       CM.collectInstsToScalarize(VF);
   }
 
   buildVPlansWithVPRecipes(1, MaxVF);
   LLVM_DEBUG(printPlans(dbgs()));
   if (MaxVF == 1)

llvm/test/Transforms/LoopVectorize/pr43371-optsize-scevchecks.ll

+; RUN: opt -S -loop-vectorize  -pass-remarks-analysis='loop-vectorize' < %s 2>&1 | FileCheck %s
+
+@cm_array = external global [2592 x i16], align 1
+
+define void @pr43371() optsize {
+;
+; remark: <unknown>:0:0: Optimizing for size, but overflow checks are emitted. Can this be avoided by e.g. using a larger loop induction variable type?
+
+; CHECK-LABEL: @pr43371
+;
+; FIXME: SCEV checks need to emitted. So when optimizing for size, we shouldn't
+; vectorize this.
+;
+; CHECK: vector.scevcheck:
+; CHECK: vector.body:
+;
+entry:
+  br label %for.body
+
+for.cond.for.cond.cleanup_crit_edge:
+  br label %for.body29
+
+for.body:
+  br label %for.cond.for.cond.cleanup_crit_edge
+
+for.cond.cleanup28:
+  unreachable
+
+for.body29:
+  %i24.0170 = phi i16 [ 0, %for.cond.for.cond.cleanup_crit_edge ], [ %inc37, %for.inc36 ]
+  %add33 = add i16 undef, %i24.0170
+  %idxprom34 = zext i16 %add33 to i32
+  %arrayidx35 = getelementptr [2592 x i16], [2592 x i16] * @cm_array, i32 0, i32 %idxprom34
+  store i16 0, i16 * %arrayidx35, align 1
+  br label %for.inc36
+
+for.inc36:
+  %inc37 = add i16 %i24.0170, 1
+  %cmp26 = icmp ult i16 %inc37, 756
+  br i1 %cmp26, label %for.body29, label %for.cond.cleanup28
+}