[LV] Report multiple reasons for not vectorizing under allowExtraAnalysis

[Ayal]

Summary

Report multiple reasons for not vectorizing a loop instead of stopping and reporting the first reason only, under ORE->allowExtraAnalysis() - via Clang's -fsave-optimization-record or opt's -pass-remarks-missed.

Removed checking and reporting if we CantComputeNumberOfIterations from LoopVectorizationLegality::canVectorize(), as
LAI::canAnalyzeLoop() is doing so, called by canVectorizeMemory(). This redundancy is caught by a lit test once multiple reasons are reported. Can be committed separately.

Patch initially developed by Dror Barak.

[fhahn]

lib/Transforms/Vectorize/LoopVectorize.cpp

5212

I think the comment also needs updating, mentioning the ORE->allowExtraAnalysis() case

[Ayal]

Fixed comment and updated documentation.

[Ayal]

lib/Transforms/Vectorize/LoopVectorize.cpp

5212

OK, sure.

Additional documentation that needs updating is docs/Vectorizers.rst.

Fixed both and uploaded updated version.

[hfinkel]

LGTM

lib/Transforms/Vectorize/LoopVectorize.cpp

5089

Please add a comment here explaining that we use this for the allowExtraAnalysis case where we don't early-exit.

[anemet]

This is a good idea. LGTM too.

test/Transforms/LoopVectorize/X86/vectorization-remarks-missed.ll

45–46

I think this is pretty meaningless without source line info. Why don't you add new DILocation metadata with unique source line numbers specifically for the loop so that you can check them here.

This test is also weirdly structured because there is no easy way to tie back source lines for the remarks to the corresponding function. Can you reorder this while you're here, like this?:

; source code 1
; CHECK: ...

; source code 2
; CHECK: ...

etc?

[anemet]

docs/Vectorizers.rst

101–103

I am curious what others think but I am not sure we want to advertise this, i.e. this is more of a bug than a feature. After PR32352 this should work even without -fsave-optimization-record.

[hfinkel]

docs/Vectorizers.rst

101–103

I agree (it is more of a bug than a feature), but on the other hand, documenting it leads to fewer surprises (hopefully). We might add, "(this behavior might change in the future)" to make this clear.

[anemet]

docs/Vectorizers.rst

101–103

SGTM

[Ayal]

Thanks @anemet and @hfinkel!
Uploaded updated version addressing all comments, to be committed.

docs/Vectorizers.rst

 
 Optimization remarks are enabled using:
 
 ``-Rpass=loop-vectorize`` identifies loops that were successfully vectorized.
 
 ``-Rpass-missed=loop-vectorize`` identifies loops that failed vectorization and
 indicates if vectorization was specified.
 
 ``-Rpass-analysis=loop-vectorize`` identifies the statements that caused
-vectorization to fail.
+vectorization to fail. If in addition ``-fsave-optimization-record`` is
+provided, multiple causes of vectorization failure may be listed.
 
 Consider the following loop:
 
 .. code-block:: c++
 
   #pragma clang loop vectorize(enable)
   for (int i = 0; i < Length; i++) {
     switch(A[i]) {

lib/Transforms/Vectorize/LoopVectorize.cpp

for (BasicBlock *BB : TheLoop->blocks()) {
     }
   }
 
   // We can if-convert this loop.
   return true;
 }
 
 bool LoopVectorizationLegality::canVectorize() {
+  bool Result = true;
   // We must have a loop in canonical form. Loops with indirectbr in them cannot
   // be canonicalized.
   if (!TheLoop->getLoopPreheader()) {
     ORE->emit(createMissedAnalysis("CFGNotUnderstood")
               << "loop control flow is not understood by vectorizer");
+    if (ORE->allowExtraAnalysis())
+      Result = false;
+    else
       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()) {
     ORE->emit(createMissedAnalysis("NotInnermostLoop")
               << "loop is not the innermost loop");
+    if (ORE->allowExtraAnalysis())
+      Result = false;
+    else
       return false;
   }
 
   // We must have a single backedge.
   if (TheLoop->getNumBackEdges() != 1) {
     ORE->emit(createMissedAnalysis("CFGNotUnderstood")
               << "loop control flow is not understood by vectorizer");
+    if (ORE->allowExtraAnalysis())
+      Result = false;
+    else
       return false;
   }
 
   // We must have a single exiting block.
   if (!TheLoop->getExitingBlock()) {
     ORE->emit(createMissedAnalysis("CFGNotUnderstood")
               << "loop control flow is not understood by vectorizer");
+    if (ORE->allowExtraAnalysis())
+      Result = false;
+    else
       return false;
   }
 
   // We only handle bottom-tested loops, i.e. loop in which the condition is
   // checked at the end of each iteration. With that we can assume that all
   // instructions in the loop are executed the same number of times.
   if (TheLoop->getExitingBlock() != TheLoop->getLoopLatch()) {
     ORE->emit(createMissedAnalysis("CFGNotUnderstood")
               << "loop control flow is not understood by vectorizer");
+    if (ORE->allowExtraAnalysis())
+      Result = false;
+    else
       return false;
   }
 
   // We need to have a loop header.
   DEBUG(dbgs() << "LV: Found a loop: " << TheLoop->getHeader()->getName()
                << '\n');
 
   // Check if we can if-convert non-single-bb loops.
   unsigned NumBlocks = TheLoop->getNumBlocks();
   if (NumBlocks != 1 && !canVectorizeWithIfConvert()) {
     DEBUG(dbgs() << "LV: Can't if-convert the loop.\n");
-    return false;
-  }
-
-  // ScalarEvolution needs to be able to find the exit count.
-  const SCEV *ExitCount = PSE.getBackedgeTakenCount();
-  if (ExitCount == PSE.getSE()->getCouldNotCompute()) {
-    ORE->emit(createMissedAnalysis("CantComputeNumberOfIterations")
-              << "could not determine number of loop iterations");
-    DEBUG(dbgs() << "LV: SCEV could not compute the loop exit count.\n");
+    if (ORE->allowExtraAnalysis())
+      Result = false;
+    else
       return false;
   }
 
   // Check if we can vectorize the instructions and CFG in this loop.
   if (!canVectorizeInstrs()) {
     DEBUG(dbgs() << "LV: Can't vectorize the instructions or CFG\n");
+    if (ORE->allowExtraAnalysis())
+      Result = false;
+    else
       return false;
   }
 
   // Go over each instruction and look at memory deps.
   if (!canVectorizeMemory()) {
     DEBUG(dbgs() << "LV: Can't vectorize due to memory conflicts\n");
+    if (ORE->allowExtraAnalysis())
+      Result = false;
+    else
       return false;
   }
 
   DEBUG(dbgs() << "LV: We can vectorize this loop"
                << (LAI->getRuntimePointerChecking()->Need
                        ? " (with a runtime bound check)"
                        : "")
                << "!\n");
 
bool LoopVectorizationLegality::canVectorize() {
   if (Hints->getForce() == LoopVectorizeHints::FK_Enabled)
     SCEVThreshold = PragmaVectorizeSCEVCheckThreshold;
 
   if (PSE.getUnionPredicate().getComplexity() > SCEVThreshold) {
     ORE->emit(createMissedAnalysis("TooManySCEVRunTimeChecks")
               << "Too many SCEV assumptions need to be made and checked "
               << "at runtime");
     DEBUG(dbgs() << "LV: Too many SCEV checks needed.\n");
+    if (ORE->allowExtraAnalysis())
+      Result = false;
+    else
       return false;
   }
 
-  // Okay! We can vectorize. At this point we don't have any other mem analysis
+  // 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.
-  return true;
+  return Result;
 }
 
 static Type *convertPointerToIntegerType(const DataLayout &DL, Type *Ty) {
   if (Ty->isPointerTy())
     return DL.getIntPtrType(Ty);
 
   // It is possible that char's or short's overflow when we ask for the loop's
   // trip count, work around this by changing the type size.

test/Transforms/LoopVectorize/X86/vectorization-remarks-missed.ll

 ; }
 
 ; void test_array_bounds(int *A, int *B, int Length) {
 ; #pragma clang loop vectorize(enable)
 ;   for (int i = 0; i < Length; i++)
 ;     A[i] = A[B[i]];
 ; }
 
+; int foo();
+; void test_multiple_failures(int *A) {
+;   int k = 0;
+; #pragma clang loop vectorize(enable) interleave(enable)
+;   for (int i = 0; i < 1000; i+=A[i]) {
+;     if (A[i])
+;       k = foo();
+;   }
+;   return k;
+; }
+
 ; File, line, and column should match those specified in the metadata
 ; CHECK: remark: source.cpp:4:5: loop not vectorized: could not determine number of loop iterations
 ; CHECK: remark: source.cpp:4:5: loop not vectorized
 ; CHECK: remark: source.cpp:13:5: loop not vectorized: vectorization and interleaving are explicitly disabled, or vectorize width and interleave count are both set to 1
 ; CHECK: remark: source.cpp:19:5: loop not vectorized: cannot identify array bounds
 ; CHECK: remark: source.cpp:19:5: loop not vectorized
 ; CHECK: warning: source.cpp:19:5: loop not vectorized: failed explicitly specified loop vectorization
+; CHECK: remark: <unknown>:0:0: loop not vectorized: control flow cannot be substituted for a select
+; CHECK: remark: <unknown>:0:0: loop not vectorized
 
 ; CHECK: _Z4testPii
 ; CHECK-NOT: x i32>
 ; CHECK: ret
 
 ; CHECK: _Z13test_disabledPii
 ; CHECK-NOT: x i32>
 ; CHECK: ret
 
 ; CHECK: _Z17test_array_boundsPiS_i
 ; CHECK-NOT: x i32>
 ; CHECK: ret
 
+; CHECK: test_multiple_failure
+; CHECK-NOT: x i32>
+; CHECK: ret
+
 ; YAML:       --- !Analysis
 ; YAML-NEXT: Pass:            loop-vectorize
 ; YAML-NEXT: Name:            CantComputeNumberOfIterations
 ; YAML-NEXT: DebugLoc:        { File: source.cpp, Line: 4, Column: 5 }
 ; YAML-NEXT: Function:        _Z4testPii
 ; YAML-NEXT: Args:
 ; YAML-NEXT:   - String:          'loop not vectorized: '
 ; YAML-NEXT:   - String:          could not determine number of loop iterations

 ; YAML-NEXT: Pass:            loop-vectorize
 ; YAML-NEXT: Name:            FailedRequestedVectorization
 ; YAML-NEXT: DebugLoc:        { File: source.cpp, Line: 19, Column: 5 }
 ; YAML-NEXT: Function:        _Z17test_array_boundsPiS_i
 ; YAML-NEXT: Args:
 ; YAML-NEXT:   - String:          'loop not vectorized: '
 ; YAML-NEXT:   - String:          failed explicitly specified loop vectorization
 ; YAML-NEXT: ...
+; YAML-NEXT: --- !Analysis
+; YAML-NEXT: Pass:            loop-vectorize
+; YAML-NEXT: Name:            NoCFGForSelect
+; YAML-NEXT: Function:        test_multiple_failures
+; YAML-NEXT: Args:
+; YAML-NEXT:   - String:          'loop not vectorized: '
+; YAML-NEXT:   - String:          control flow cannot be substituted for a select
+; YAML-NEXT: ...
+; YAML-NEXT: --- !Analysis
+; YAML-NEXT: Pass:            loop-vectorize
+; YAML-NEXT: Name:            NonReductionValueUsedOutsideLoop
+; YAML-NEXT: Function:        test_multiple_failures
+; YAML-NEXT: Args:
+; YAML-NEXT:   - String:          'loop not vectorized: '
+; YAML-NEXT:   - String:          value that could not be identified as reduction is used outside the loop
+; YAML-NEXT: ...
+; YAML-NEXT: --- !Analysis
+; YAML-NEXT: Pass:            loop-vectorize
+; YAML-NEXT: Name:            CantComputeNumberOfIterations
+; YAML-NEXT: Function:        test_multiple_failures
+; YAML-NEXT: Args:
+; YAML-NEXT:   - String:          'loop not vectorized: '
+; YAML-NEXT:   - String:          could not determine number of loop iterations
+; YAML-NEXT: ...
+; YAML-NEXT: --- !Missed
+; YAML-NEXT: Pass:            loop-vectorize
+; YAML-NEXT: Name:            MissedDetails
+; YAML-NEXT: Function:        test_multiple_failures
+; YAML-NEXT: Args:
+; YAML-NEXT:   - String:          loop not vectorized
+; YAML-NEXT: ...
 
 target datalayout = "e-m:o-i64:64-f80:128-n8:16:32:64-S128"
 
 ; Function Attrs: nounwind optsize ssp uwtable
 define void @_Z4testPii(i32* nocapture %A, i32 %Length) #0 !dbg !4 {
 entry:
   %cmp10 = icmp sgt i32 %Length, 0, !dbg !12
   br i1 %cmp10, label %for.body, label %for.end, !dbg !12, !llvm.loop !14

 
 for.end.loopexit:                                 ; preds = %for.body
   br label %for.end
 
 for.end:                                          ; preds = %for.end.loopexit, %entry
   ret void, !dbg !36
 }
 
+; Function Attrs: nounwind uwtable
+define i32 @test_multiple_failures(i32* nocapture readonly %A) #0 {
+entry:
+  br label %for.body
+
+for.body:                                         ; preds = %entry, %for.inc
+  %i.09 = phi i32 [ 0, %entry ], [ %add, %for.inc ]
+  %k.09 = phi i32 [ 0, %entry ], [ %k.1, %for.inc ]
+  %arrayidx = getelementptr inbounds i32, i32* %A, i32 %i.09
+  %0 = load i32, i32* %arrayidx, align 4
+  %tobool = icmp eq i32 %0, 0
+  br i1 %tobool, label %for.inc, label %if.then
+
+if.then:                                          ; preds = %for.body
+  %call = tail call i32 (...) @foo()
+  %.pre = load i32, i32* %arrayidx, align 4
+  br label %for.inc
+
+for.inc:                                          ; preds = %for.body, %if.then
+  %1 = phi i32 [ %.pre, %if.then ], [ 0, %for.body ]
+  %k.1 = phi i32 [ %call, %if.then ], [ %k.09, %for.body ]
+  %add = add nsw i32 %1, %i.09
+  %cmp = icmp slt i32 %add, 1000
+  br i1 %cmp, label %for.body, label %for.cond.cleanup
+
+for.cond.cleanup:                                 ; preds = %for.inc
+  ret i32 %k.1
+}
+
+declare i32 @foo(...)
+
 attributes #0 = { nounwind }
 
 !llvm.dbg.cu = !{!0}
 !llvm.module.flags = !{!9, !10}
 !llvm.ident = !{!11}
 
 !0 = distinct !DICompileUnit(language: DW_LANG_C_plus_plus, producer: "clang version 3.5.0", isOptimized: true, runtimeVersion: 6, emissionKind: LineTablesOnly, file: !1, enums: !2, retainedTypes: !2, globals: !2, imports: !2)
 !1 = !DIFile(filename: "source.cpp", directory: ".")