[LoopVectorize] Detect loops in the innermost loop before creating InnerLoopVectorizer

[timshen]

Summary

InnerLoopVectorizer shouldn't handle a loop with cycles inside the loop
body, even if that cycle isn't a natural loop.

Fixes PR28541.

[nadav]

lib/Transforms/Vectorize/LoopVectorize.cpp

6726 ↗

(On Diff #66071)

Is this the correct way to add this check? This looks like a check that needs to be a part of the legality check. Also, we should probably emit a debug message or something.

[timshen]

Move the check to canVectorize().

[nadav]

lib/Transforms/Vectorize/LoopVectorize.cpp

4555 ↗

(On Diff #66379)

I think that the new message is less informative. Please make this two separate checks. One for cycles and the other message for non-innermost.

I don't have any other comments.

[mkuper]

test/Transforms/LoopVectorize/pr28541.ll

3 ↗

(On Diff #66379)

Could you also please check that the loop doesn't get vectorized?

[anemet]

Where this check should be is related to PR28374. I think it should be checked when we initially gather the inner most loops in addInnerLoop.

test/Transforms/LoopVectorize/pr28541.ll

1 ↗

(On Diff #66379)

Use -loop-vectorize rather than -O2.

3 ↗

(On Diff #66379)

+1 and if you pass -pass-remarks-missed=loop-vectorize you can also check that the diag message is emitted correctly

[mkuper]

In D22952#502880, @anemet wrote:

Where this check should be is related to PR28374. I think it should be checked when we initially gather the inner most loops in addInnerLoop.

I'm not sure. I mean, both ways make sense, but the way I see it is the inner-most "loop", in the sense that there are no loops (as opposed to cycles) living inside it. So adding it, and then performing a legality check makes sense to me.
What's the motivation for doing it in addInnerLoop? I don't see why that would improve reporting, and I think it'd be nicer to leave addInnerLoop straight-forward, and keep all of the negative conditions in the legality check.

[anemet]

In D22952#503039, @mkuper wrote:

In D22952#502880, @anemet wrote:

Where this check should be is related to PR28374. I think it should be checked when we initially gather the inner most loops in addInnerLoop.

I'm not sure. I mean, both ways make sense, but the way I see it is the inner-most "loop", in the sense that there are no loops (as opposed to cycles) living inside it. So adding it, and then performing a legality check makes sense to me.
What's the motivation for doing it in addInnerLoop? I don't see why that would improve reporting, and I think it'd be nicer to leave addInnerLoop straight-forward, and keep all of the negative conditions in the legality check.

I guess it all depends on whether you think these checks are similar or not. I don't really see the difference between loops and cycles. For example, when I look at the testcase in C, I essentially see two nested loops even though the inner one is a bit weird (I guess it's multi-entry). I am not sure that it make sense to differentiate the two to the user either.

Thus I'd like to have a single place where we check for the inner-most loop property (with LoopInfo and beyond) and where we properly report back to the user. This is currently addInnerLoop. (The other place is dead before the patch, AFAICT.)

[chandlerc]

In D22952#503046, @anemet wrote:

I guess it all depends on whether you think these checks are similar or not. I don't really see the difference between loops and cycles. For example, when I look at the testcase in C, I essentially see two nested loops even though the inner one is a bit weird (I guess it's multi-entry). I am not sure that it make sense to differentiate the two to the user either.

Thus I'd like to have a single place where we check for the inner-most loop property (with LoopInfo and beyond) and where we properly report back to the user. This is currently addInnerLoop. (The other place is dead before the patch, AFAICT.)

At a somewhat fundamental level, LLVM uses the term "loop" to mean "natural loop", and not any arbitrary cycle. Similarly, throughout LoopInfo and the loop pass manager we model "inner loop" as the innermost natural loop, regardless of whether there are cycles nested within it.

So while I don't have a really strong opinion about how the vectorizer is factored (I don't really work on it) I would expect an LLVM API spelled "addInnerLoop" to mean "add inner natural loop" and not "add inner cycle which happens to be a natural loop" or "add inner loop that doesn't contain a cycle".

It is possible we could work to change LLVM's terminology, but I think that'd be a pretty big shift. So, if you want to filter these things in "addInnerLoop" I'd suggest trying to find a more precise name.

[anemet]

In D22952#503062, @chandlerc wrote:

At a somewhat fundamental level, LLVM uses the term "loop" to mean "natural loop", and not any arbitrary cycle. Similarly, throughout LoopInfo and the loop pass manager we model "inner loop" as the innermost natural loop, regardless of whether there are cycles nested within it.

So while I don't have a really strong opinion about how the vectorizer is factored (I don't really work on it) I would expect an LLVM API spelled "addInnerLoop" to mean "add inner natural loop" and not "add inner cycle which happens to be a natural loop" or "add inner loop that doesn't contain a cycle".

It is possible we could work to change LLVM's terminology, but I think that'd be a pretty big shift. So, if you want to filter these things in "addInnerLoop" I'd suggest trying to find a more precise name.

Sure, I would be certainly OK changing the name if that is misleading.

I look at this more from the POV of which one is conservatively more correct?

I think that in addInnerLoop, adding a loop that actually has another non-natural loop nested is more error-prone than not. I actually believe that we have other (inner-most) loop optimizations that have the same bug as the vectorizer that use a similar code to enumerate inner-most loops. Thus it would probably be better to have a central utility that gives you natural loops that are guaranteed to have an acyclic body (whatever the name is), i.e. inner-most in the most conservative sense.

[timshen]

Updated tests, and pull out hasCycleInLoopBody.

[timshen]

Add FileCheck invoke to the testcase.

[timshen]

I think that in addInnerLoop, adding a loop that actually has another non-natural loop nested is more error-prone than not. I actually believe that we have other (inner-most) loop optimizations that have the same bug as the vectorizer that use a similar code to enumerate inner-most loops. Thus it would probably be better to have a central utility that gives you natural loops that are guaranteed to have an acyclic body (whatever the name is), i.e. inner-most in the most conservative sense.

Maybe we can do this in another patch, and have an exhaustive discussion there? I moved hasCycleInLoopBody out, so that the intended change to addInnerLoop is one-line.

[mkuper]

The LV change LGTM, although if anemet strongly prefers to move this out of the legality check, and into addInnerLoop, I can live with that.

I really don't know enough about graph traits to pass judgement on that. One thing I can say is that I have the nagging suspicion LoopBodyTraits should live somewhere closer to LoopInfo, and not in LoopVectorizer.cpp.

test/Transforms/LoopVectorize/pr28541.ll

25 ↗

(On Diff #66867)

This doesn't look like it ought to work if you're only passing -loop-vectorize to opt.
Presumably, to get any kind of output except IR, you'd need either -debug (in which case you'd have to require asserts), or, as Adam suggested, -pass-remarks-missed. I agree with Adam - what you want is pass-remarks, and to check that you get "the loop body has a cycle".

[mkuper]

test/Transforms/LoopVectorize/pr28541.ll

26 ↗

(On Diff #66870)

Sorry, ignore this, commented before the last change. :-)

[anemet]

In D22952#506383, @mkuper wrote:

The LV change LGTM, although if anemet strongly prefers to move this out of the legality check, and into addInnerLoop, I can live with that.

Thanks, Michael. Yes, that would be my preference. We need to change the name though to avoid the ambiguity with loop <-> natural loop. AddLoopWithAcyclicBody?

I really don't know enough about graph traits to pass judgement on that. One thing I can say is that I have the nagging suspicion LoopBodyTraits should live somewhere closer to LoopInfo, and not in LoopVectorizer.cpp.

This is new to me too but looks pretty interesting so will stare at it more tomorrow.

[timshen]

addInnerLoop -> addAcyclicInnerLoop

[anemet]

lib/Transforms/Vectorize/LoopVectorize.cpp

224–226 ↗

(On Diff #67001)

I think that we want to say it here a bit more explicitly that the reason you skip the loop header so that the backedges are excluded from the graph.

230 ↗

(On Diff #67001)

Add a comment that this is wrapped in order to 'package' a constant Loop inside the iterator.

246 ↗

(On Diff #67001)

I don't think we use 'this' in such cases.

249–254 ↗

(On Diff #67001)

Can this be a predicate function instead?

262–265 ↗

(On Diff #67001)

Actually a more basic question. Why can't we filter succ_iterator directly i.e. just by passing the loop to LoopBodyFilter here?

1919–1924 ↗

(On Diff #67001)

This would be the place to emit the optimization remark (emitAnalysis)

4635–4638 ↗

(On Diff #67001)

You no longer need this.

test/Transforms/LoopVectorize/pr28541.ll

1 ↗

(On Diff #67001)

Why did you change from -pass-remaks-missed to -pass-remarks? I prefer positive checks over negative ones.

I think that we also want to check the particular reason for failing to vectorize, so please also pass -pass-remarks-analysis=loop-vectorize and check for that string as well.

[timshen]

Updated comments for LoopBodyTraits.

lib/Transforms/Vectorize/LoopVectorize.cpp

249–254 ↗

(On Diff #67001)

If the predicate is a function, then to use it we have to pass it around as a function pointer, which is more expensive because of the dynamic dispatch. If we have a huge loop body it may end up with effecting the performance.

262–265 ↗

(On Diff #67001)

Because we want to do the filtering lazily, don't we? If we filter succ_iterator here by LoopBodyFilter, we have to create a container to hold the filtered results (so that later operator++() and operator*() can inspect those results), which is less efficient. I went for the efficient way without sacrifice the readability (?).

1919–1924 ↗

(On Diff #67001)

There are two problems revealed by this addInnerLoop -> addAcyclicInnerLoop change.

First, since addAcyclicInnerLoop gets called in LoopVectorizePass::runImpl, where no report/analysis infrastructure is set up, it's pretty hard to call emitAnalysis here.

Secondly, a loop with a cycle in its body never gets into LoopVectorizePass::processLoop, so nothing is logged through -pass-remarks-missed. That's why I have to check for -pass-remarks in the test case.

4635–4638 ↗

(On Diff #67001)

Could LoopVectorizationLegality be used in anywhere else, where addAcyclicInnerLoop doesn't guard?

test/Transforms/LoopVectorize/pr28541.ll

1 ↗

(On Diff #67001)

Why did you change from -pass-remaks-missed to -pass-remarks? I prefer positive checks over negative ones.

See the comments for addAcyclicInnerLoop.

[hans]

Who is this blocked on? anemet?

[timshen]

In D22952#513286, @hans wrote:

Who is this blocked on? anemet?

Blocked by D22951, so dblaikie. :)

[timshen]

In D22952#513290, @timshen wrote:

Blocked by D22951, so dblaikie. :)

Sorry, dblaikie and anemet. I post some comments in the last round.

[anemet]

I'll look at this today. @hans, is this for 3.9 or what's the rush?

[hans]

In D22952#513297, @anemet wrote:

I'll look at this today. @hans, is this for 3.9 or what's the rush?

Yes, the PR is a 3.9 blocker. There's no immediate rush, I'm just trying to make sure things keep moving along :-)

[anemet]

lib/Transforms/Vectorize/LoopVectorize.cpp

262–265 ↗

(On Diff #67250)

I am not sure we're talking about the same thing. I meant:

return make_filter_range(make_range<succ_iterator>(
                                          succ_begin(Node.second),
                                          succ_end(Node.second)),
                                        LoopBodyFilter(Node.first))

and then:

struct LoopBodyFilter {
  LoopBodyFitler(Loop *L) : L(L) {}
  bool operator()(BasicBlock *BB) const {
    return BB != L->getHeader() && L->contains(BB);
  }
  Loop *L;
};

?

In other words, it does not seem any different to me whether you attach the loop to the succ_iterator or the filter object.

[anemet]

lib/Transforms/Vectorize/LoopVectorize.cpp

1922–1928 ↗

(On Diff #67250)

It seem to me that nothing prevents us from letting all loops go all the way until Legality.canVectorize(). Then we can check this property as the very first thing in there.

If that does not work we can check this earlier in processLoop.

The part we're missing to report diagnostics in addAcyclicInnerLoop is the Hints which provides the pass name. Alternatively, we can also construct Hints in addAcyclicInnerLoop. This is probably the least preferred alternative though because then you need to propagate this back to processLoop.

[timshen]

lib/Transforms/Vectorize/LoopVectorize.cpp

1922–1928 ↗

(On Diff #67250)

It seem to me that nothing prevents us from letting all loops go all the way until Legality.canVectorize(). Then we can check this property as the very first thing in there.

I think the point of addInnerLoop, rather than addAllLoops, is to make the Worklist smaller. So if we want to let all loops go all the way until Legality::canVectorize(), there is a potential compilation performance change and also an analysis change.

I'm fine with changing addInnerLoop to addInnerAcyclicLoop, because it more or less is related to this patch, and it doesn't have a performance impact; but changing the "take innermost loop only" assumption of LoopVectorizePass::processLoop is too much.

I think your concern should be addressed in a separate patch.

[anemet]

lib/Transforms/Vectorize/LoopVectorize.cpp

1922–1928 ↗

(On Diff #67250)

OK. There is no regression in the optimization diagnostic quality with this patch so I am fine with doing it later.

4638–4641 ↗

(On Diff #67250)

No.

test/Transforms/LoopVectorize/pr28541.ll

2 ↗

(On Diff #67250)

Then please add a FIXME about this.

[timshen]

Added FIXME into the test.

[timshen]

lib/Transforms/Vectorize/LoopVectorize.cpp

4638–4641 ↗

(On Diff #67250)

Removed.

[anemet]

LGTM with the change below.

lib/Transforms/Vectorize/LoopVectorize.cpp

4630–4634 ↗

(On Diff #67923)

Please add a FIXME, that this code is dead too as we discovered (unless you will remove it in a quick follow-up).

[timshen]

Added a FIXME into canVectorize() on innertmost loop check.

[timshen]

lib/Transforms/Vectorize/LoopVectorize.cpp

4630–4634 ↗

(On Diff #67923)

I added a FIXME, since it's unclear to me if it's a good idea to remove things from canVectorize() - this function seems to do all kinds of centralized checking, regardless of the caller side situation.

I'll leave the potential actual removal in the future, possibly after a discussion.

[anemet]

lib/Transforms/Vectorize/LoopVectorize.cpp

4633–4637 ↗

(On Diff #67927)

OK.

For the record, there is already the PR I quoted above about not reporting anything for non-inner-most loops.

[timshen]

Thank you all for reviewing!

llvm/trunk/lib/Transforms/Vectorize/LoopVectorize.cpp

 //  Vectorizing Compilers.
 //
 //===----------------------------------------------------------------------===//
 
 #include "llvm/Transforms/Vectorize/LoopVectorize.h"
 #include "llvm/ADT/DenseMap.h"
 #include "llvm/ADT/Hashing.h"
 #include "llvm/ADT/MapVector.h"
+#include "llvm/ADT/SCCIterator.h"
 #include "llvm/ADT/SetVector.h"
 #include "llvm/ADT/SmallPtrSet.h"
 #include "llvm/ADT/SmallSet.h"
 #include "llvm/ADT/SmallVector.h"
 #include "llvm/ADT/Statistic.h"
 #include "llvm/ADT/StringExtras.h"
 #include "llvm/Analysis/CodeMetrics.h"
 #include "llvm/Analysis/GlobalsModRef.h"

 namespace {
 
 // Forward declarations.
 class LoopVectorizeHints;
 class LoopVectorizationLegality;
 class LoopVectorizationCostModel;
 class LoopVectorizationRequirements;
 
+// A traits type that is intended to be used in graph algorithms. The graph it
+// models starts at the loop header, and traverses the BasicBlocks that are in
+// the loop body, but not the loop header. Since the loop header is skipped,
+// the back edges are excluded.
+struct LoopBodyTraits {
+  using NodeRef = std::pair<const Loop *, BasicBlock *>;
+
+  // This wraps a const Loop * into the iterator, so we know which edges to
+  // filter out.
+  class WrappedSuccIterator
+      : public iterator_adaptor_base<
+            WrappedSuccIterator, succ_iterator,
+            typename std::iterator_traits<succ_iterator>::iterator_category,
+            NodeRef, std::ptrdiff_t, NodeRef *, NodeRef> {
+    using BaseT = iterator_adaptor_base<
+        WrappedSuccIterator, succ_iterator,
+        typename std::iterator_traits<succ_iterator>::iterator_category,
+        NodeRef, std::ptrdiff_t, NodeRef *, NodeRef>;
+
+    const Loop *L;
+
+  public:
+    WrappedSuccIterator(succ_iterator Begin, const Loop *L)
+        : BaseT(Begin), L(L) {}
+
+    NodeRef operator*() const { return {L, *I}; }
+  };
+
+  struct LoopBodyFilter {
+    bool operator()(NodeRef N) const {
+      const Loop *L = N.first;
+      return N.second != L->getHeader() && L->contains(N.second);
+    }
+  };
+
+  using ChildIteratorType =
+      filter_iterator<WrappedSuccIterator, LoopBodyFilter>;
+
+  static NodeRef getEntryNode(const Loop &G) { return {&G, G.getHeader()}; }
+
+  static ChildIteratorType child_begin(NodeRef Node) {
+    return make_filter_range(make_range<WrappedSuccIterator>(
+                                 {succ_begin(Node.second), Node.first},
+                                 {succ_end(Node.second), Node.first}),
+                             LoopBodyFilter{})
+        .begin();
+  }
+
+  static ChildIteratorType child_end(NodeRef Node) {
+    return make_filter_range(make_range<WrappedSuccIterator>(
+                                 {succ_begin(Node.second), Node.first},
+                                 {succ_end(Node.second), Node.first}),
+                             LoopBodyFilter{})
+        .end();
+  }
+};
+
+/// Returns true if the given loop body has a cycle, excluding the loop
+/// itself.
+static bool hasCyclesInLoopBody(const Loop &L) {
+  if (!L.empty())
+    return true;
+
+  for (const auto SCC :
+       make_range(scc_iterator<Loop, LoopBodyTraits>::begin(L),
+                  scc_iterator<Loop, LoopBodyTraits>::end(L))) {
+    if (SCC.size() > 1) {
+      DEBUG(dbgs() << "LVL: Detected a cycle in the loop body:\n");
+      DEBUG(L.dump());
+      return true;
+    }
+  }
+  return false;
+}
+
 /// \brief This modifies LoopAccessReport to initialize message with
 /// loop-vectorizer-specific part.
 class VectorizationReport : public LoopAccessReport {
 public:
   VectorizationReport(Instruction *I = nullptr)
       : LoopAccessReport("loop not vectorized: ", I) {}
 
   /// \brief This allows promotion of the loop-access analysis report into the

 private:
   unsigned NumRuntimePointerChecks;
   Instruction *UnsafeAlgebraInst;
 
   /// Interface to emit optimization remarks.
   OptimizationRemarkEmitter &ORE;
 };
 
-static void addInnerLoop(Loop &L, SmallVectorImpl<Loop *> &V) {
-  if (L.empty())
-    return V.push_back(&L);
-
+static void addAcyclicInnerLoop(Loop &L, SmallVectorImpl<Loop *> &V) {
+  if (L.empty()) {
+    if (!hasCyclesInLoopBody(L))
+      V.push_back(&L);
+    return;
+  }
   for (Loop *InnerL : L)
-    addInnerLoop(*InnerL, V);
+    addAcyclicInnerLoop(*InnerL, V);
 }
 
 /// The LoopVectorize Pass.
 struct LoopVectorize : public FunctionPass {
   /// Pass identification, replacement for typeid
   static char ID;
 
   explicit LoopVectorize(bool NoUnrolling = false, bool AlwaysVectorize = true)
bool LoopVectorizationLegality::canVectorize() {
   // We must have a loop in canonical form. Loops with indirectbr in them cannot
   // be canonicalized.
   if (!TheLoop->getLoopPreheader()) {
     emitAnalysis(VectorizationReport()
                  << "loop control flow is not understood by vectorizer");
     return false;
   }
 
+  // FIXME: The code is currently dead, since the loop gets sent to
+  // LoopVectorizationLegality is already an innermost loop.
+  //
   // We can only vectorize innermost loops.
   if (!TheLoop->empty()) {
     emitAnalysis(VectorizationReport() << "loop is not the innermost loop");
     return false;
   }
 
   // We must have a single backedge.
   if (TheLoop->getNumBackEdges() != 1) {
if (!TTI->getNumberOfRegisters(true) && TTI->getMaxInterleaveFactor(1) < 2)
     return false;
 
   // Build up a worklist of inner-loops to vectorize. This is necessary as
   // the act of vectorizing or partially unrolling a loop creates new loops
   // and can invalidate iterators across the loops.
   SmallVector<Loop *, 8> Worklist;
 
   for (Loop *L : *LI)
-    addInnerLoop(*L, Worklist);
+    addAcyclicInnerLoop(*L, Worklist);
 
   LoopsAnalyzed += Worklist.size();
 
   // Now walk the identified inner loops.
   bool Changed = false;
   while (!Worklist.empty())
     Changed |= processLoop(Worklist.pop_back_val());
 

llvm/trunk/test/Transforms/LoopVectorize/pr28541.ll

+; RUN: opt -loop-vectorize -pass-remarks=loop-vectorize -S < %s 2>&1 | FileCheck %s
+
+; FIXME: Check for -pass-remarks-missed and -pass-remarks-analysis output when
+; addAcyclicInnerLoop emits analysis.
+
+; Check that opt does not crash on such input:
+;
+; a, b, c;
+; fn1() {
+;   while (b--) {
+;     c = a;
+;     switch (a & 3)
+;     case 0:
+;       do
+;     case 3:
+;     case 2:
+;     case 1:
+;         ;
+;         while (--c)
+;           ;
+;   }
+; }
+
+@b = common global i32 0, align 4
+@a = common global i32 0, align 4
+@c = common global i32 0, align 4
+
+; CHECK-NOT: vectorized loop
+; CHECK-LABEL: fn1
+
+define i32 @fn1() {
+entry:
+  %tmp2 = load i32, i32* @b, align 4
+  %dec3 = add nsw i32 %tmp2, -1
+  store i32 %dec3, i32* @b, align 4
+  %tobool4 = icmp eq i32 %tmp2, 0
+  br i1 %tobool4, label %while.end, label %while.body.lr.ph
+
+while.body.lr.ph:                                 ; preds = %entry
+  %tmp1 = load i32, i32* @a, align 4
+  %and = and i32 %tmp1, 3
+  %switch = icmp eq i32 %and, 0
+  br label %while.body
+
+while.cond:                                       ; preds = %do.cond
+  %dec = add nsw i32 %dec7, -1
+  %tobool = icmp eq i32 %dec7, 0
+  br i1 %tobool, label %while.cond.while.end_crit_edge, label %while.body
+
+while.body:                                       ; preds = %while.body.lr.ph, %while.cond
+  %dec7 = phi i32 [ %dec3, %while.body.lr.ph ], [ %dec, %while.cond ]
+  br i1 %switch, label %do.body, label %do.cond
+
+do.body:                                          ; preds = %do.cond, %while.body
+  %dec25 = phi i32 [ %dec2, %do.cond ], [ %tmp1, %while.body ]
+  br label %do.cond
+
+do.cond:                                          ; preds = %do.body, %while.body
+  %dec26 = phi i32 [ %dec25, %do.body ], [ %tmp1, %while.body ]
+  %dec2 = add nsw i32 %dec26, -1
+  %tobool3 = icmp eq i32 %dec2, 0
+  br i1 %tobool3, label %while.cond, label %do.body
+
+while.cond.while.end_crit_edge:                   ; preds = %while.cond
+  store i32 0, i32* @c, align 4
+  store i32 -1, i32* @b, align 4
+  br label %while.end
+
+while.end:                                        ; preds = %while.cond.while.end_crit_edge, %entry
+  ret i32 undef
+}