Handle Top-Level-Regions in polly::isHoistableLoad

[lksbhm]

Summary

This can be seen as a follow-up on my previous differential D33411.
We received a bug report where this error was triggered. I have tried my best to recreate the issue in a minimal lit testcase which is also part of this differential.

I only handle return instructions as predecessors to a virtual TLR-exit right now. From inspecting the codebase, it seems unreachable instructions may also be of interest here. If requested, I can extend my patches to consider them as well. I would also apply this on ScopHelper.cpp::isErrorBlock (see D33411), of course.

[lksbhm]

Remove attribute from memcpy decl and add newline at end of file

[lksbhm]

Remove FileCheck component from RUN line which caused the test to fail. Sorry

[philip.pfaffe]

LGTM.

@bollu: Can you verify that this fixes your issue?

[Meinersbur]

test/ScopDetect/tlr_is_hoistable_load.ll

1–3 ↗

(On Diff #124378)

It would be nice to have a line that describes what this is testing. We usually also add FileCheck/CHECK lines to verify the expected output.

[lksbhm]

test/ScopDetect/tlr_is_hoistable_load.ll

1–3 ↗

(On Diff #124378)

Thank you for your feedback! Yes, I would also like to use FileCheck here, but the expected output is pretty boring - just a bunch of "Invalid Scop!" lines. That's why I actively removed the FileCheck call (see reason for second update). If you think this would still be beneficial, I have no objections to adding some CHECK lines, though.

Regardless of that, a small comment at the top of the file describing the intention of the test case sounds like a good idea. But I find it difficult to come up with a meaningful description aside from that I want to cover the code path where the error occurs. Maybe the description should focus on the exotic combination of cli options this test is run with?

This also leads me to the question if ScopDetect is the best location for this test. I chose it because from the call stack in gdb, ScopDetection was the pipeline stage at which the call to isHoistableLoad is made. If you have recommendations for a better location, I would be glad to hear them and move the test file accordingly.

[lksbhm]

• Remove unneeded & duplicate polly arguments from the test run line
• Re-add FileCheck with a few simple CHECK lines to the test
• Add a description at the top of the test file

[bollu]

Other than request for documentation, LGTM. I did not test it, but I reduced the test case with bugpoint, so it should be the right fix. If not, I can complain again ;)

lib/Support/ScopHelper.cpp

475 ↗

(On Diff #124551)

Could you please add a link to the test case? I'm not sure what the Polly convention on this is, but having a reference to what code path this covers would be helpful in the future :) Something like this is what I have in mind

[philip.pfaffe]

lib/Support/ScopHelper.cpp

475 ↗

(On Diff #124551)

I really don't like the idea. Is there precedent for this in polly or llvm (besides the one @bollu posted)?

polly/trunk/lib/Support/ScopHelper.cpp

for (auto *User : Ptr->users()) {
     if (!UserI->mayWriteToMemory())
       continue;
 
     auto &BB = *UserI->getParent();
     if (DT.dominates(&BB, LInst->getParent()))
       return false;
 
     bool DominatesAllPredecessors = true;
+    if (R.isTopLevelRegion()) {
+      for (BasicBlock &I : *R.getEntry()->getParent())
+        if (isa<ReturnInst>(I.getTerminator()) && !DT.dominates(&BB, &I))
+          DominatesAllPredecessors = false;
+    } else {
       for (auto Pred : predecessors(R.getExit()))
         if (R.contains(Pred) && !DT.dominates(&BB, Pred))
           DominatesAllPredecessors = false;
+    }
 
     if (!DominatesAllPredecessors)
       continue;
 
     return false;
   }
 
   return true;

polly/trunk/test/ScopDetect/tlr_is_hoistable_load.ll

+; RUN: opt %loadPolly -analyze -polly-scops -polly-invariant-load-hoisting \
+; RUN:     -polly-detect-full-functions < %s | FileCheck %s
+;
+; This testcase checks for compatibility of the -detect-full-functions
+; flag in combination with the -invariant-load-hoisting option. More
+; specifically, ScopHelper.cpp::isHoistableLoad only gets called if
+; -invariant-load-hoisting is enabled. This function, however, had a bug
+; which caused a crash if the region argument was top-level. This test
+; is a minimal example that hits this specific code path.
+;
+; Also note that this file's IR is in no way optimized, i.e. it was
+; generated with clang -O0 from the following C-code:
+;
+;    void test() {
+;      int A[] = {1, 2, 3, 4, 5};
+;      int len = (sizeof A) / sizeof(int);
+;      for (int i = 0; i < len; ++i) {
+;        A[i] = A[i] * 2;
+;      }
+;    }
+;
+; This is also the reason why polly does not detect any scops (the loop
+; variable i is loaded from and stored to memory in each iteration):
+;
+; CHECK:      region: 'for.cond => for.end' in function 'test':
+; CHECK-NEXT: Invalid Scop!
+; CHECK-NEXT: region: 'entry => <Function Return>' in function 'test':
+; CHECK-NEXT: Invalid Scop!
+;
+target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
+
+@test.A = private unnamed_addr constant [5 x i32] [i32 1, i32 2, i32 3, i32 4, i32 5], align 16
+
+define void @test() {
+entry:
+  %A = alloca [5 x i32], align 16
+  %len = alloca i32, align 4
+  %i = alloca i32, align 4
+  %0 = bitcast [5 x i32]* %A to i8*
+  call void @llvm.memcpy.p0i8.p0i8.i64(i8* %0, i8* bitcast ([5 x i32]* @test.A to i8*), i64 20, i32 16, i1 false)
+  store i32 5, i32* %len, align 4
+  store i32 0, i32* %i, align 4
+  br label %for.cond
+
+for.cond:                                         ; preds = %for.inc, %entry
+  %1 = load i32, i32* %i, align 4
+  %2 = load i32, i32* %len, align 4
+  %cmp = icmp slt i32 %1, %2
+  br i1 %cmp, label %for.body, label %for.end
+
+for.body:                                         ; preds = %for.cond
+  %3 = load i32, i32* %i, align 4
+  %idxprom = sext i32 %3 to i64
+  %arrayidx = getelementptr inbounds [5 x i32], [5 x i32]* %A, i64 0, i64 %idxprom
+  %4 = load i32, i32* %arrayidx, align 4
+  %mul = mul nsw i32 %4, 2
+  %5 = load i32, i32* %i, align 4
+  %idxprom1 = sext i32 %5 to i64
+  %arrayidx2 = getelementptr inbounds [5 x i32], [5 x i32]* %A, i64 0, i64 %idxprom1
+  store i32 %mul, i32* %arrayidx2, align 4
+  br label %for.inc
+
+for.inc:                                          ; preds = %for.body
+  %6 = load i32, i32* %i, align 4
+  %inc = add nsw i32 %6, 1
+  store i32 %inc, i32* %i, align 4
+  br label %for.cond
+
+for.end:                                          ; preds = %for.cond
+  ret void
+}
+
+declare void @llvm.memcpy.p0i8.p0i8.i64(i8* nocapture writeonly, i8* nocapture readonly, i64, i32, i1)