[CodeGen] Emit parallel_loop_access for each loop in the loop stack.

[Meinersbur]

Summary

Emit !llvm.mem.parallel_loop_access metadata for memory accesses even if the parallel loop is not the top on the loop stack.

Fixes llvm.org/PR37558.

[ABataev]

I don't think that this is the intended behavior of the #pragma clang loop. it is better to ask the author of this pragma is this correct or not.

[hfinkel]

In D48808#1149534, @ABataev wrote:

I don't think that this is the intended behavior of the #pragma clang loop. it is better to ask the author of this pragma is this correct or not.

It is the intended behavior that the memory accesses are independent with respect to the outer (annotated) loop (even if those accesses are within an inner loop). They're not independent with respect to the inner loop unless that loop is also annotated. Thus, this looks correct.

Michael, can you please add a test with two inner loops, one where more than one is annotated, and one where only the outer loop is annotated? It's not clear to me that I->setMetadata will do the right thing here in the former case.

[Meinersbur]

In D48808#1149534, @ABataev wrote:

I don't think that this is the intended behavior of the #pragma clang loop. it is better to ask the author of this pragma is this correct or not.

I understand it as the intended behavior of the assume_safety option (also used for #pragma omp simd).

@tyler.nowicki What is the intended behaviour?

[tyler.nowicki]

Hi Michael, Hal,

Sorry it has been a while since I looked at this. My memory is a little
fuzzy. The intent of 'assume_safety' is to tell LAA to skip dependency
checking on loads and stores so the vectorizer doesn't stop as soon as it
sees both in a loop. At the time 'assume_safety' was implemented the
vectorizer was limited to inner-loops. I am not up-to-date but it seems to
have the ability to perform some vectorization of non-inner loop
instructions?

If we can vectorize non-inner loop instructions then what behavior would
make the most sense: 'assume_safety' applies to the same loop scope(s) as
the other loop pragmas, or it applies to all nested loops?

My opinion is that for consistency 'assume_safety' and similar options
apply to the same scope(s) as 'vectorize(enable)'. But I am open to
alternatives if others see it differently.

Tyler Nowicki

[Meinersbur]

In D48808#1149549, @hfinkel wrote:

In D48808#1149534, @ABataev wrote:

Michael, can you please add a test with two inner loops, one where more than one is annotated, and one where only the outer loop is annotated? It's not clear to me that I->setMetadata will do the right thing here in the former case.

The test case pragma-loop-safety-nested.cpp check the case where the outer loop is annotated.

Iterating over Active will iterate from outer to inner loops, meaning I->setMetadata will overwrite the annotation of the outermost loop (which IMHO is the most useful behaviour). Since it not possible to add multiple !llvm.mem.parallel_loop_access annotation, we cannot annotate multiple loops.

[hfinkel]

In D48808#1149828, @Meinersbur wrote:

In D48808#1149549, @hfinkel wrote:

In D48808#1149534, @ABataev wrote:

Michael, can you please add a test with two inner loops, one where more than one is annotated, and one where only the outer loop is annotated? It's not clear to me that I->setMetadata will do the right thing here in the former case.

The test case pragma-loop-safety-nested.cpp check the case where the outer loop is annotated.

Iterating over Active will iterate from outer to inner loops, meaning I->setMetadata will overwrite the annotation of the outermost loop (which IMHO is the most useful behaviour). Since it not possible to add multiple !llvm.mem.parallel_loop_access annotation, we cannot annotate multiple loops.

We specifically defined the metadata to support nested loops. The LangRef says, "The llvm.mem.parallel_loop_access metadata refers to a loop identifier, or metadata containing a list of loop identifiers for nested loops." To handle nested loops, we need to make the instruction metadata point to a list of loop IDs.

[Meinersbur]

In D48808#1149845, @hfinkel wrote:

We specifically defined the metadata to support nested loops. The LangRef says, "The llvm.mem.parallel_loop_access metadata refers to a loop identifier, or metadata containing a list of loop identifiers for nested loops." To handle nested loops, we need to make the instruction metadata point to a list of loop IDs.

Thanks for pointing me to it. I've not seen parallel_loop_access pointing to a list, so I didn't know it was possible.

[hfinkel]

In D48808#1149862, @Meinersbur wrote:

In D48808#1149845, @hfinkel wrote:

We specifically defined the metadata to support nested loops. The LangRef says, "The llvm.mem.parallel_loop_access metadata refers to a loop identifier, or metadata containing a list of loop identifiers for nested loops." To handle nested loops, we need to make the instruction metadata point to a list of loop IDs.

Thanks for pointing me to it. I've not seen parallel_loop_access pointing to a list, so I didn't know it was possible.

Yea, well, we defined it to be possible. As to whether the backend will actually correctly read the metadata in that format, I don't know.

[Meinersbur]

• Allow multiple parallel annotations

[Meinersbur]

• Adapt test file message.

[Meinersbur]

• Hoist I->mayReadOrWriteMemory() condition.

[Meinersbur]

ping

[Meinersbur]

ping

[hfinkel]

LGTM

lib/CodeGen/CGLoopInfo.cpp

if (TerminatorInst *TI = dyn_cast<TerminatorInst>(I)) {
     for (unsigned i = 0, ie = TI->getNumSuccessors(); i < ie; ++i)
       if (TI->getSuccessor(i) == L.getHeader()) {
         TI->setMetadata(llvm::LLVMContext::MD_loop, L.getLoopID());
         break;
       }
     return;
   }
 
-  if (L.getAttributes().IsParallel && I->mayReadOrWriteMemory())
-    I->setMetadata("llvm.mem.parallel_loop_access", L.getLoopID());
+  if (I->mayReadOrWriteMemory()) {
+    SmallVector<Metadata *, 2> ParallelLoopIDs;
+    for (const LoopInfo &AL : Active)
+      if (AL.getAttributes().IsParallel)
+        ParallelLoopIDs.push_back(AL.getLoopID());
+
+    MDNode *ParallelMD = nullptr;
+    if (ParallelLoopIDs.size() == 1)
+      ParallelMD = cast<MDNode>(ParallelLoopIDs[0]);
+    else if (ParallelLoopIDs.size() >= 2)
+      ParallelMD = MDNode::get(I->getContext(), ParallelLoopIDs);
+    I->setMetadata("llvm.mem.parallel_loop_access", ParallelMD);
+  }
 }

test/CodeGenCXX/pragma-loop-safety-nested.cpp

+// RUN: %clang_cc1 -triple x86_64-apple-darwin -std=c++11 -emit-llvm -o - %s | FileCheck %s
+
+// Verify that the inner access is tagged with a parallel_loop_access
+// for the inner and outer loop using a list.
+void vectorize_nested_test(int *List, int Length) {
+#pragma clang loop vectorize(assume_safety) interleave(disable) unroll(disable)
+  for (int i = 0; i < Length; ++i) {
+#pragma clang loop vectorize(assume_safety) interleave(disable) unroll(disable)
+    for (int j = 0; j < Length; ++j)
+      List[i * Length + j] = (i + j) * 2;
+  }
+}
+
+// CHECK: %[[MUL:.+]] = mul
+// CHECK: store i32 %[[MUL]], i32* %{{.+}}, !llvm.mem.parallel_loop_access ![[PARALLEL_LIST:[0-9]+]]
+// CHECK: br label %{{.+}}, !llvm.loop ![[INNER_LOOPID:[0-9]+]]
+// CHECK: br label %{{.+}}, !llvm.loop ![[OUTER_LOOPID:[0-9]+]]
+
+// CHECK: ![[OUTER_LOOPID]] = distinct !{![[OUTER_LOOPID]],
+// CHECK: ![[PARALLEL_LIST]] = !{![[OUTER_LOOPID]], ![[INNER_LOOPID]]}
+// CHECK: ![[INNER_LOOPID]] = distinct !{![[INNER_LOOPID]],

test/CodeGenCXX/pragma-loop-safety-outer.cpp

+// RUN: %clang_cc1 -triple x86_64-apple-darwin -std=c++11 -emit-llvm -o - %s | FileCheck %s
+
+// Verify that the inner access is tagged with a parallel_loop_access
+// for the outer loop.
+void vectorize_outer_test(int *List, int Length) {
+#pragma clang loop vectorize(assume_safety) interleave(disable) unroll(disable)
+  for (int i = 0; i < Length; i += 2) {
+#pragma clang loop unroll(full)
+    for (int j = 0; j < 2; j += 1)
+      List[i + j] = (i + j) * 2;
+  }
+}
+
+// CHECK: %[[MUL:.+]] = mul
+// CHECK: store i32 %[[MUL]], i32* %{{.+}}, !llvm.mem.parallel_loop_access ![[OUTER_LOOPID:[0-9]+]]
+// CHECK: br label %{{.+}}, !llvm.loop ![[INNER_LOOPID:[0-9]+]]
+// CHECK: br label %{{.+}}, !llvm.loop ![[OUTER_LOOPID]]
+
+// CHECK: ![[OUTER_LOOPID]] = distinct !{![[OUTER_LOOPID]],
+// CHECK: ![[INNER_LOOPID]] = distinct !{![[INNER_LOOPID]],