[LV] Look through PHIs when collecting uniform values

[mkuper]

Summary

The motivation is in the test-case: currently, we miss %indvars.iv.next, because it can not be reached by walking backwards from the branch.

[mkuper]

test/Transforms/LoopVectorize/X86/uniform-phi.ll

7

And this is probably wrong, for the same reason as http://reviews.llvm.org/D20474#inline-183502
We want to look through the PHI, but we don't want to mark the PHI itself uniform. I'll update the patch.

[mkuper]

Abandoning this in favor of http://reviews.llvm.org/D21755

lib/Transforms/Vectorize/LoopVectorize.cpp

bool LoopVectorizationLegality::canVectorizeInstrs() {
 
   return true;
 }
 
 void LoopVectorizationLegality::collectLoopUniforms() {
   // We now know that the loop is vectorizable!
   // Collect variables that will remain uniform after vectorization.
   std::vector<Value *> Worklist;
+  SmallPtrSet<Value *, 4> VisitedPHIs;
   BasicBlock *Latch = TheLoop->getLoopLatch();
 
   // Start with the conditional branch and walk up the block.
   Worklist.push_back(Latch->getTerminator()->getOperand(0));
 
   // Also add all consecutive pointer values; these values will be uniform
   // after vectorization (and subsequent cleanup) and, until revectorization is
   // supported, all dependencies must also be uniform.
   for (Loop::block_iterator B = TheLoop->block_begin(),
                             BE = TheLoop->block_end();
        B != BE; ++B)
     for (BasicBlock::iterator I = (*B)->begin(), IE = (*B)->end(); I != IE; ++I)
       if (I->getType()->isPointerTy() && isConsecutivePtr(&*I))
         Worklist.insert(Worklist.end(), I->op_begin(), I->op_end());
 
   while (!Worklist.empty()) {
     Instruction *I = dyn_cast<Instruction>(Worklist.back());
     Worklist.pop_back();
 
     // Look at instructions inside this loop.
-    // Stop when reaching PHI nodes.
     // TODO: we need to follow values all over the loop, not only in this block.
-    if (!I || !TheLoop->contains(I) || isa<PHINode>(I))
+    if (!I || !TheLoop->contains(I))
+      continue;
+
+    // Look through each PHI node only once, to avoid infinite loops.
+    if (isa<PHINode>(I) && !VisitedPHIs.insert(I).second)
       continue;
 
     // This is a known uniform.
     Uniforms.insert(I);
+    DEBUG(dbgs() << "LV: Found uniform instruction: " << *I << "\n");
 
     // Insert all operands.
     Worklist.insert(Worklist.end(), I->op_begin(), I->op_end());
   }
 }
 
 bool LoopVectorizationLegality::canVectorizeMemory() {
   LAI = &LAA->getInfo(TheLoop);

test/Transforms/LoopVectorize/X86/uniform-phi.ll

+; RUN: opt < %s  -loop-vectorize -mtriple=x86_64-apple-macosx10.8.0 -mcpu=corei7 -debug-only=loop-vectorize -S 2>&1 | FileCheck %s
+; REQUIRES: asserts
+target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
+target triple = "x86_64-unknown-linux-gnu"
+
+; CHECK-LABEL: test
+; CHECK: LV: Found uniform instruction:   %indvars.iv = phi i64 [ 0, %entry ], [ %indvars.iv.next, %for.body ]
+; CHECK: LV: Found uniform instruction:   %indvars.iv.next = add nuw nsw i64 %indvars.iv, 1
+; CHECK: LV: Found uniform instruction:   %exitcond = icmp eq i64 %indvars.iv, 1599
+
+define void @test(float* noalias nocapture %a, float* noalias nocapture readonly %b) #0 {
+entry:
+  br label %for.body
+
+for.body:                                         ; preds = %for.body, %entry
+  %indvars.iv = phi i64 [ 0, %entry ], [ %indvars.iv.next, %for.body ]
+  %arrayidx = getelementptr inbounds float, float* %b, i64 %indvars.iv
+  %0 = load float, float* %arrayidx, align 4
+  %add = fadd float %0, 1.000000e+00
+  %arrayidx5 = getelementptr inbounds float, float* %a, i64 %indvars.iv
+  store float %add, float* %arrayidx5, align 4
+  %indvars.iv.next = add nuw nsw i64 %indvars.iv, 1
+  %exitcond = icmp eq i64 %indvars.iv, 1599
+  br i1 %exitcond, label %for.end, label %for.body
+
+for.end:                                          ; preds = %for.body
+  ret void
+}