[Vectorization] Actually return from error case in isStridedPtr

[timshen]

Summary

The early return seems to be missed. This causes a radical and wrong loop optimization on powerpc. It isn't reproducible on x86_64, because "UseInterleaved" is false.

[majnemer]

This test case is a bit large, can it be made smaller?

test/Analysis/LoopAccessAnalysis/interleave_innermost.ll

1

You can shorten this pipeline with:
; RUN: opt -O2 -S < %s | FileCheck %s

[timshen]

Done.

In order to reproduce the bug, it seems to require a nested loop structure. I've reduced the test file to 54 lines, in which the nested loops are pretty obvious to me. Do you think that's simple enough?

[timshen]

Mark previous comment as done.

[mzolotukhin]

The change itself looks good, but there are several things about the test that could be improved:

1. I think you don't need to run the entire O2 pipeline on the test. For instance, if the offending optimization is "loop-vectorizer", we could extract IR before it, and replace opt -O2 with opt -loop-vectorize on this IR (to find the list of the O2 passes, run opt -O2 -debug-pass=Arguments).
2. Do you use CHECK + XFAIL only to make sure that the specified lines aren't present in the output? Could you use CHECK-NOT instead? Also, if you run only one pass, it will be much easier to check that nothing unexpected happened with the IR.
3. Could you please run opt -instnamer on the IR to avoid %123 and <label>:123 names? It's very painful to edit tests with such variable names (as the numbers must be consecutive).
4. Minor point: you probably could remove function attributes.

Thanks,
Michael

[timshen]

Done. These are really useful options! Thanks!

[majnemer]

FWIW, the following also triggers the missing early return with opt -loop-vectorize

target datalayout = "e-m:e-i64:64-n32:64"
target triple = "powerpc64le-unknown-linux-gnu"

define void @TestFoo(i1 %X, i1 %Y) {
bb:
  br label %.loopexit5.outer

.loopexit5.outer:
  br label %.lr.ph12

.loopexit:
  br i1 %X, label %.loopexit5.outer, label %.lr.ph12

.lr.ph12:
  %f.110 = phi i32* [ %tmp1, %.loopexit ], [ null, %.loopexit5.outer ]
  %tmp1 = getelementptr inbounds i32, i32* %f.110, i64 -1
  br i1 %Y, label %bb4, label %.loopexit

bb4:
  %j.27 = phi i32 [ 0, %.lr.ph12 ], [ %tmp7, %bb4 ]
  %tmp5 = load i32, i32* %f.110, align 4
  %tmp7 = add nsw i32 %j.27, 1
  %exitcond = icmp eq i32 %tmp7, 0
  br i1 %exitcond, label %.loopexit, label %bb4
}

test/Analysis/LoopAccessAnalysis/interleave_innermost.ll

2

Is -instcombine necessary here?

[timshen]

Yes, your test case is much simpler, thanks! :) I tweaked a bit (stride needs to be at least 2 to trigger interleave) to reveal the wrong behavior of the old opt. In such case it has to be a XFAIL, since what we hope is "interleave should not fire" - testing the correct code may be fragile.

[timshen]

test/Analysis/LoopAccessAnalysis/interleave_innermost.ll

2

Not applicable. It was necessary, otherwise the old opt produces correct code.

3

Not applicable. It was necessary, otherwise the old opt produces correct code.

[echristo]

Check not?

[timshen]

In D15906#320222, @echristo wrote:

Check not?

I'm not sure - can I use CHECK-NOT(s) for a multi-line pattern?

A bit thinking: semantically I want not (LINE_PATTERN_1 and LINE_PATTERN_2 and LINE_PATTERN3), which means I may do something roughly like (not LINE_PATTERN_1) or (not LINE_PATTERN_2) or (not LINE_PATTERN_3), not LINE_PATTERNx can be expressed as CHECK-NOT, but I'm not sure if we have a way to express or.

[timshen]

Removed XFAIL and CHECK-NOT for interleave related value names - if XFAIL doesn't seem to be used in such a scenario.

[echristo]

I don't think that you can CHECK-NOT two things in a row like this. You'll need a check between. In general for this you should be able to just check that there aren't any vector types in the program? Or you could add something in between as well.

-eric

[timshen]

I think CHECK-NOT for "wide.vec" is good enough.

[echristo]

Seems reasonable to me as well.

-eric

[timshen]

Thanks iteratee for committing as r257134 !

lib/Analysis/LoopAccessAnalysis.cpp

DEBUG(dbgs() << "LAA: Bad stride - Not an AddRecExpr pointer "
           << *Ptr << " SCEV: " << *PtrScev << "\n");
     return 0;
   }
 
   // The accesss function must stride over the innermost loop.
   if (Lp != AR->getLoop()) {
     DEBUG(dbgs() << "LAA: Bad stride - Not striding over innermost loop " <<
           *Ptr << " SCEV: " << *PtrScev << "\n");
+    return 0;
   }
 
   // The address calculation must not wrap. Otherwise, a dependence could be
   // inverted.
   // An inbounds getelementptr that is a AddRec with a unit stride
   // cannot wrap per definition. The unit stride requirement is checked later.
   // An getelementptr without an inbounds attribute and unit stride would have
   // to access the pointer value "0" which is undefined behavior in address

test/Analysis/LoopAccessAnalysis/interleave_innermost.ll

+; RUN: opt -O2 %s | llvm-dis | FileCheck %s
+; CHECK: %[[ENTRY:[0-9]+]] = getelementptr inbounds %StructA, %StructA* %{{[^ ]+}}, i64 -1, i32 1
+; CHECK: bitcast i32* %[[ENTRY]] to <{{[0-9]+}} x i32>*
+; XFAIL: *
+
+target datalayout = "e-m:e-i64:64-n32:64"
+target triple = "powerpc64le-unknown-linux-gnu"
+
+%StructA = type { i8, i32 }
+
+@GlobalA = external global [5 x [64 x i32]], align 4
+@GLobalB = external global [1 x %StructA*], align 8
+@Entry = external global [2 x %StructA], align 4
+
+define void @_ZN4borgL16BuildReasonTableEv() {
+  %i = alloca i32, align 4
+  %field = alloca %StructA*, align 8
+  %f = alloca %StructA*, align 8
+  %r = alloca i32*, align 8
+  %width = alloca i32, align 4
+  %j = alloca i32, align 4
+  store i32 0, i32* %i, align 4
+  br label %1
+
+; <label>:1                                       ; preds = %33, %0
+  %2 = load i32, i32* %i, align 4
+  %3 = icmp slt i32 %2, 5
+  br i1 %3, label %4, label %34
+
+; <label>:4                                       ; preds = %1
+  %5 = getelementptr inbounds [1 x %StructA*], [1 x %StructA*]* @GLobalB, i64 0, i64 undef
+  %6 = load %StructA*, %StructA** %5, align 8
+  store %StructA* %6, %StructA** %field, align 8
+  br label %7
+
+; <label>:7                                       ; preds = %8, %4
+  br i1 undef, label %8, label %9
+
+; <label>:8                                       ; preds = %7
+  br label %7
+
+; <label>:9                                       ; preds = %7
+  %10 = load i32, i32* %i, align 4
+  br label %11
+
+; <label>:11                                      ; preds = %21, %9
+  %12 = load %StructA*, %StructA** %f, align 8
+  %13 = load %StructA*, %StructA** %field, align 8
+  %14 = icmp ne %StructA* %12, %13
+  br i1 %14, label %15, label %33
+
+; <label>:15                                      ; preds = %11
+  %16 = load %StructA*, %StructA** %f, align 8
+  %17 = getelementptr inbounds %StructA, %StructA* %16, i32 -1
+  store %StructA* %17, %StructA** %f, align 8
+  %18 = getelementptr inbounds %StructA, %StructA* %17, i32 0, i32 0
+  %19 = load i8, i8* %18, align 4
+  %20 = sext i8 %19 to i32
+  store i32 %20, i32* %width, align 4
+  br label %21
+
+; <label>:21                                      ; preds = %25, %15
+  %22 = load i32, i32* %j, align 4
+  %23 = load i32, i32* %width, align 4
+  %24 = icmp slt i32 %22, %23
+  br i1 %24, label %25, label %11
+
+; <label>:25                                      ; preds = %21
+  %26 = load %StructA*, %StructA** %f, align 8
+  %27 = getelementptr inbounds %StructA, %StructA* %26, i32 0, i32 1
+  %28 = load i32, i32* %27, align 4
+  %29 = load i32*, i32** %r, align 8
+  %30 = getelementptr inbounds i32, i32* %29, i32 1
+  store i32* %30, i32** %r, align 8
+  store i32 %28, i32* %29, align 4
+  %31 = load i32, i32* %j, align 4
+  %32 = add nsw i32 %31, 1
+  store i32 %32, i32* %j, align 4
+  br label %21
+
+; <label>:33                                      ; preds = %11
+  br label %1
+
+; <label>:34                                      ; preds = %1
+  ret void
+}