Filter UnDef size values in Scop Detection

[cs14mtech11017]

Summary

Currently, there is an assert on undef size value in polly::MemoryAccess::foldAccess().
It is better to restrict them in ScopDetection itself.

[grosser]

Hi Utpal,

thanks for your work.

The patch itself looks good, but could you please include a test case in
the patch. Also, please run make polly-check-format to see if your formatting
is correct or run make polly-update-format to fix it if it did not match
the LLVM style already.

Best,
Tobias

[grosser]

Also, please add the next time llvm-commits and polly-dev as a subscriber.

[cs14mtech11017]

In D11425#210032, @grosser wrote:

Hi Utpal,

thanks for your work.

The patch itself looks good, but could you please include a test case in

Where can I upload the test case?

the patch. Also, please run make polly-check-format to see if your formatting
is correct or run make polly-update-format to fix it if it did not match
the LLVM style already.

Yes there was differences in formatting. I have corrected it. Thanks for letting me know.

Best,
Tobias

[grosser]

In D11425#210640, @cs14mtech11017 wrote:

In D11425#210032, @grosser wrote:

Hi Utpal,

thanks for your work.

The patch itself looks good, but could you please include a test case in

Where can I upload the test case?

Add it to the test/ directory in Polly and make sure it passes 'make check'.

Then commit it to your git repository and upload a new patch that contains both your code changes as well as your test case to phabricator.

Best,
Tobias

[cs14mtech11017]

Hi Tobias,

Some test cases are failing with this patch and I am stuck trying to fix one of them. Please see my details below-

With this undef patch, 24 regression test cases are failing.

1. Run make check-all

24 test cases are failing.

2. One among them is Polly :: ScopInfo/multidim_srem.ll

3. Run llvm-lit (with the patch)

llvm-lit -v tools/polly/test/ScopInfo/multidim_srem.ll

The output is as attached below -

Command Output (stderr):

/home/cs14mtech11017/llvm_latest/llvm/tools/polly/test/ScopInfo/multidim_srem.ll:11:10: error: expected string not found in input
; CHECK: [n] -> { Stmt_for_body_8[i0, i1, i2] -> MemRef_A[o0, i1, i2] : exists (e0 = floor((-i0 + o0)/2): 2e0 = -i0 + o0 and o0 >= 0 and o0 <= 1) };

^

<stdin>:26:2: note: scanning from here
[n, p_1, p_2] -> { Stmt_for_body_8[i0] -> MemRef_A[o0] : 4o0 = 4p_1 + p_2 + 4i0 };
^

4. I compared the output of this test case with and without the patch. In both the cases, the output is exactly the same. I am confused why llvm-lit is failing with the patch. Please see the two outputs below.

polly-opt -analyze -polly-scops -S ~/llvm_latest/llvm/tools/polly/test/ScopInfo/multidim_srem.ll

a. Output with patch
Statements {

    Stmt_for_body_8
        Domain :=
            [n] -> { Stmt_for_body_8[i0, i1, i2] : i0 >= 0 and i0 <= 199 and i1 >= 0 and i1 <= -1 + n and i2 >= 0 and i2 <= -1 + n and n >= 1 };
        Schedule :=
            [n] -> { Stmt_for_body_8[i0, i1, i2] -> [i0, i1, i2] };
        ReadAccess :=       [Reduction Type: NONE] [Scalar: 0]
            [n] -> { Stmt_for_body_8[i0, i1, i2] -> MemRef_A[o0, i1, i2] : exists (e0 = floor((-i0 + o0)/2): 2e0 = -i0 + o0 and o0 >= 0 and o0 <= 1) };
        MustWriteAccess :=  [Reduction Type: NONE] [Scalar: 0]
            [n] -> { Stmt_for_body_8[i0, i1, i2] -> MemRef_A[o0, i1, i2] : exists (e0 = floor((-i0 + o0)/2): 2e0 = -i0 + o0 and o0 >= 0 and o0 <= 1) };
}

b. Output without patch
Statements {

    Stmt_for_body_8
        Domain :=
            [n] -> { Stmt_for_body_8[i0, i1, i2] : i0 >= 0 and i0 <= 199 and i1 >= 0 and i1 <= -1 + n and i2 >= 0 and i2 <= -1 + n and n >= 1 };
        Schedule :=
            [n] -> { Stmt_for_body_8[i0, i1, i2] -> [i0, i1, i2] };
        ReadAccess :=       [Reduction Type: NONE] [Scalar: 0]
            [n] -> { Stmt_for_body_8[i0, i1, i2] -> MemRef_A[o0, i1, i2] : exists (e0 = floor((-i0 + o0)/2): 2e0 = -i0 + o0 and o0 >= 0 and o0 <= 1) };
        MustWriteAccess :=  [Reduction Type: NONE] [Scalar: 0]
            [n] -> { Stmt_for_body_8[i0, i1, i2] -> MemRef_A[o0, i1, i2] : exists (e0 = floor((-i0 + o0)/2): 2e0 = -i0 + o0 and o0 >= 0 and o0 <= 1) };
}

[grosser]

With your patch I get the following output:

Statements {
	Stmt_for_body_8
        Domain :=
            [n, p_1, p_2] -> { Stmt_for_body_8[i0] : i0 >= 0 and i0 <= -1 + n };
        Schedule :=
            [n, p_1, p_2] -> { Stmt_for_body_8[i0] -> [i0] };
        ReadAccess :=	[Reduction Type: NONE] [Scalar: 0]
            [n, p_1, p_2] -> { Stmt_for_body_8[i0] -> MemRef_A[o0] : 4o0 = 4p_1 + p_2 + 4i0 };
        MustWriteAccess :=	[Reduction Type: NONE] [Scalar: 0]
            [n, p_1, p_2] -> { Stmt_for_body_8[i0] -> MemRef_A[o0] : 4o0 = 4p_1 + p_2 + 4i0 };
}

This means the delinearization fails.

I checked your code. It is wrong. The 'return false' is not part of the innermost condition, as you forgot
to add the braces around the if and the if consequently only includes the next instruction:

if (auto *Unknown = dyn_cast<SCEVUnknown>(DelinearizedSize)){
     auto *value = dyn_cast<Value>(Unknown->getValue());
    ​ if (isa<UndefValue>(value))
​         invalid<ReportDifferentArrayElementSize>(Context, /*Assert=*/true,
​                                                                   Context.Accesses[BasePointer].front().first, BaseValue);
         return false  << Not part of if
}

[cs14mtech11017]

Yes I saw that now. Thanks for catching it so quickly. Now all the test cases are passing.

[grosser]

OK. Can you then please update your patch and also include a test case, such that we can commit both.

Thank you,
Tobias

[cs14mtech11017]

Filter UnDef size values in Scop Detection.

[grosser]

LGTM.

I will commit this as soon as the LLVM servers are back (they seem to be done ATM).

polly/trunk/lib/Analysis/ScopDetection.cpp

for (const auto &Pair : Context.Accesses[BasePointer]) {
       }
     }
 
     // Second step: find array shape.
     SE->findArrayDimensions(Terms, Shape->DelinearizedSizes,
                             Context.ElementSize[BasePointer]);
 
     if (!AllowNonAffine)
-      for (const SCEV *DelinearizedSize : Shape->DelinearizedSizes)
+      for (const SCEV *DelinearizedSize : Shape->DelinearizedSizes) {
+        if (auto *Unknown = dyn_cast<SCEVUnknown>(DelinearizedSize)) {
+          auto *value = dyn_cast<Value>(Unknown->getValue());
+          if (isa<UndefValue>(value)) {
+            invalid<ReportDifferentArrayElementSize>(
+                Context, /*Assert=*/true,
+                Context.Accesses[BasePointer].front().first, BaseValue);
+            return false;
+          }
+        }
         if (hasScalarDepsInsideRegion(DelinearizedSize, &CurRegion))
           invalid<ReportNonAffineAccess>(
               Context, /*Assert=*/true, DelinearizedSize,
               Context.Accesses[BasePointer].front().first, BaseValue);
+      }
 
     // No array shape derived.
     if (Shape->DelinearizedSizes.empty()) {
       if (AllowNonAffine)
         continue;
 
       for (const auto &Pair : Context.Accesses[BasePointer]) {
         const Instruction *Insn = Pair.first;

polly/trunk/test/ScopDetect/restrict-undef-size-scopdetect.ll

+; RUN: opt %loadPolly -polly-detect -analyze  < %s | FileCheck %s
+; CHECK-NOT: Valid Region for Scop:
+
+target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
+
+%struct.bar = type { i32, [4 x i32] }
+
+define void @f(%struct.bar* %arg) {
+bb:
+  %tmp = alloca [4 x i32], align 16
+  br label %bb1
+
+bb1:                                              ; preds = %bb8, %bb
+  %tmp2 = phi i64 [ 0, %bb ], [ %tmp9, %bb8 ]
+  br i1 false, label %bb3, label %bb6
+
+bb3:                                              ; preds = %bb1
+  %tmp4 = getelementptr inbounds [4 x i32], [4 x i32]* %tmp, i64 0, i64 0
+  %tmp5 = load i32, i32* %tmp4
+  br label %bb8
+
+bb6:                                              ; preds = %bb1
+  %tmp7 = getelementptr inbounds %struct.bar, %struct.bar* %arg, i64 0, i32 1, i64 undef
+  store i32 42, i32* %tmp7
+  br label %bb8
+
+bb8:                                              ; preds = %bb6, %bb3
+  %tmp9 = add nuw nsw i64 %tmp2, 1
+  br i1 false, label %bb1, label %bb10
+
+bb10:                                             ; preds = %bb8
+  ret void
+}