[llvm] Loop Vectorization fault in collectLoopUni

[david2050]

Summary

In a large LTO build, the assert inside this loop body is triggered because Worklist is empty. This change avoids the problem and appears to successfully compile. The code appears to strongly expect the Worklist to be non-empty.

I will try to find a test case.... but any suggestions along the way would be appreciated.

[anemet]

Hi David,

You forgot to CC llvm-commits.

Adam

[Gerolf]

lib/Transforms/Vectorize/LoopVectorize.cpp

4862 ↗

(On Diff #65808)

I think it would be better to return when the worklist is empty. At this point there is nothing left to do and the compiler does not have to execute the case. We ran into the same problem and I isolated function and loop, but don't have a small test case yet.

[wmi]

Thanks for helping me fixing the bug. I think most of the cases worklist is not empty because loop condition is usually defined inside the loop, but it is possible that the loop condition is defined outside of loop. I think your fix is good.

Here is a testcase reproducing the problem:

~/workarea/llvm-r275818/dbuild/bin/opt -loop-vectorize -S < a.ll

a.ll:

define void @foo() local_unnamed_addr {
entry:
  %exitcond = icmp eq i64 3, 3
  br label %for.body

for.body:                                         ; preds = %entry
  %i.05 = phi i64 [ %inc, %for.body ], [ 0, %entry ]
  %total1 = add nsw i64 %i.05, 3
  %inc = add nuw nsw i64 %i.05, 1
  br i1 %exitcond, label %for.end, label %for.body, !llvm.loop !0

for.end:                                          ; preds = %for.body
  ret void
}

!0 = distinct !{!0, !1}
!1 = !{!"llvm.loop.vectorize.enable", i1 true}

[wmi]

lib/Transforms/Vectorize/LoopVectorize.cpp

4862 ↗

(On Diff #65808)

Even if the Worklist is empty, it is still possible that induction variable could be added into the uniform set in the following code, so I think the existing fix is better.

[wmi]

LGTM with the test added.

[david2050]

Added test case

[david2050]

Wei would you commit, I don't have permissions

[Gerolf]

Hm, FWIW this test doesn't reproduce with our compiler that exposes the problem at stage 2. And I still think when there are no uniforms within the loop there is no need to traverser the PHI nodes later.
Since the patch clearly fixes an obvious problem I'm OK with a commit even w/o a test case - LGTM.

-Gerolf

[anemet]

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

4839–4844

Hi Wei,

AFAICT, you introduced this code in D21755. It would be great if you could explain the rationale/add a comment for the isOutOfScope part (especially that it has led to this bug).

Also, was there a test added for the case of an out-of-scope condition in D21755?

Thank you,
Adam

[anemet]

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

4839–4844

@wmi, did you see this request? It's not urgent; I just wanted to make sure that it does not get lost.

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

void LoopVectorizationLegality::collectLoopUniforms() {
   // outside of the scope which we are interesting in.
   auto isOutOfScope = [&](Value *V) -> bool {
     Instruction *I = dyn_cast<Instruction>(V);
     return (!I || !TheLoop->contains(I));
   };
 
   SetVector<Instruction *> Worklist;
   BasicBlock *Latch = TheLoop->getLoopLatch();
   // Start with the conditional branch.
   if (!isOutOfScope(Latch->getTerminator()->getOperand(0))) {
     Instruction *Cmp = cast<Instruction>(Latch->getTerminator()->getOperand(0));
     Worklist.insert(Cmp);
     DEBUG(dbgs() << "LV: Found uniform instruction: " << *Cmp << "\n");
   }
 
   // Also add all consecutive pointer values; these values will be uniform
   // after vectorization (and subsequent cleanup).
   for (auto *BB : TheLoop->blocks()) {
     for (auto &I : *BB) {
       if (I.getType()->isPointerTy() && isConsecutivePtr(&I)) {
         Worklist.insert(&I);
         DEBUG(dbgs() << "LV: Found uniform instruction: " << I << "\n");
       }
     }
   }
 
   // Expand Worklist in topological order: whenever a new instruction
   // is added , its users should be either already inside Worklist, or
   // out of scope. It ensures a uniform instruction will only be used
   // by uniform instructions or out of scope instructions.
   unsigned idx = 0;
-  do {
+  while (idx != Worklist.size()) {
     Instruction *I = Worklist[idx++];
 
     for (auto OV : I->operand_values()) {
       if (isOutOfScope(OV))
         continue;
       auto *OI = cast<Instruction>(OV);
       if (all_of(OI->users(), [&](User *U) -> bool {
             return isOutOfScope(U) || Worklist.count(cast<Instruction>(U));
           })) {
         Worklist.insert(OI);
         DEBUG(dbgs() << "LV: Found uniform instruction: " << *OI << "\n");
       }
     }
-  } while (idx != Worklist.size());
+  }
 
   // For an instruction to be added into Worklist above, all its users inside
   // the current loop should be already added into Worklist. This condition
   // cannot be true for phi instructions which is always in a dependence loop.
   // Because any instruction in the dependence cycle always depends on others
   // in the cycle to be added into Worklist first, the result is no ones in
   // the cycle will be added into Worklist in the end.
   // That is why we process PHI separately.

llvm/trunk/test/Transforms/LoopVectorize/2016-07-27-loop-vec.ll

+; RUN: opt < %s -loop-vectorize -S
+
+define void @foo() local_unnamed_addr {
+entry:
+  %exitcond = icmp eq i64 3, 3
+  br label %for.body
+
+for.body:                                         ; preds = %entry
+  %i.05 = phi i64 [ %inc, %for.body ], [ 0, %entry ]
+  %total1 = add nsw i64 %i.05, 3
+  %inc = add nuw nsw i64 %i.05, 1
+  br i1 %exitcond, label %for.end, label %for.body, !llvm.loop !0
+
+for.end:                                          ; preds = %for.body
+  ret void
+}
+
+!0 = distinct !{!0, !1}
+!1 = !{!"llvm.loop.vectorize.enable", i1 true}