[Polly][IslAst] Fix minimal dependence distance.

[huihuiz]

Summary

When checking the parallelism of a scheduling dimension, we first check if excluding reduction dependences the loop is parallel or not.
If the loop is not parallel, then we need to return the minimal dependence distance of all data dependences, including the previously subtracted reduction dependences.

[Meinersbur]

LGTM

Do you need someone to commit?

[Meinersbur]

test/Isl/Ast/dependence_distance_minimal.ll

23–56

Could you run the -instnamer pass on this? Should make the statement names checked in the AST more stable.

[huihuiz]

add -instnamer to unit test

[huihuiz]

In D45236#1056334, @Meinersbur wrote:

LGTM

Do you need someone to commit?

Thank you so much!
I have commit right, hang in there, I should be committing soon.

[Meinersbur]

test/Isl/Ast/dependence_distance_minimal.ll

2

Sorry, this is not what I meant.

The instructions and BasicBlocks in this .ll file have no names, making LLVM assigning numeric "names" on the fly. Such ids are instable, and without result in different statement names for statements (Stmt1 and Stmt1_b) depending on -polly-use-llvm-names and iteration order.
Please regenerate this files _with_ string names which fixes those names to those in this file. The -instnamer pass automatically assigns string names, so you can just run this file through opt -instnamer and get a new file with instruction names.

[huihuiz]

addressing review comments

[Meinersbur]

In D45236#1056423, @huihuiz wrote:

addressing review comments

Thank you.

lib/Analysis/DependenceInfo.cpp

if (!isl_union_map_is_empty(RED)) {
 
     // Step 3)
     RAW = isl_union_map_subtract(RAW, isl_union_map_copy(RED));
     WAW = isl_union_map_subtract(WAW, isl_union_map_copy(RED));
     WAR = isl_union_map_subtract(WAR, isl_union_map_copy(RED));
 
     // Step 4)
     addPrivatizationDependences();
-  }
+  } else
+    TC_RED = isl_union_map_empty(isl_union_map_get_space(RED));
 
   DEBUG({
     dbgs() << "Final Wrapped Dependences:\n";
     dump();
     dbgs() << "\n";
   });
 
   // RED_SIN is used to collect all reduction dependences again after we

lib/CodeGen/IslAst.cpp

static bool astScheduleDimIsParallel(__isl_keep isl_ast_build *Build,
                                      IslAstUserPayload *NodeInfo) {
   if (!D->hasValidDependences())
     return false;
 
   isl_union_map *Schedule = isl_ast_build_get_schedule(Build);
   isl_union_map *Deps = D->getDependences(
       Dependences::TYPE_RAW | Dependences::TYPE_WAW | Dependences::TYPE_WAR);
 
-  if (!D->isParallel(Schedule, Deps, &NodeInfo->MinimalDependenceDistance) &&
-      !isl_union_map_free(Schedule))
+  if (!D->isParallel(Schedule, Deps)) {
+    isl_union_map *DepsAll =
+        D->getDependences(Dependences::TYPE_RAW | Dependences::TYPE_WAW |
+                          Dependences::TYPE_WAR | Dependences::TYPE_TC_RED);
+    D->isParallel(Schedule, DepsAll, &NodeInfo->MinimalDependenceDistance);
+    isl_union_map_free(Schedule);
     return false;
+  }
 
   isl_union_map *RedDeps = D->getDependences(Dependences::TYPE_TC_RED);
   if (!D->isParallel(Schedule, RedDeps))
     NodeInfo->IsReductionParallel = true;
 
   if (!NodeInfo->IsReductionParallel && !isl_union_map_free(Schedule))
     return true;
 

test/Isl/Ast/dependence_distance_minimal.ll

+; RUN: opt %loadPolly -polly-ast -polly-ast-detect-parallel -analyze < %s | FileCheck %s
+;
+; The minimal dependence distance of the innermost loop should be 1 instead of 250.
+; CHECK:    #pragma minimal dependence distance: 1
+; CHECK:    for (int c0 = 0; c0 <= 499; c0 += 1)
+; CHECK:      #pragma minimal dependence distance: 1
+; CHECK:      for (int c1 = 0; c1 <= 998; c1 += 1)
+; CHECK:        Stmt1(c0, c1);
+; CHECK:        Stmt1_b(c0, c1);
+;
+;    void foo (int *A, int *B) {
+;      for (int i=0; i < 500; i++) {
+;        for (int j=0; j < 1000; j++) {
+;          B[i] = B[i] + 1;
+;          A[j] += A[j % 250];
+;        }
+;      }
+;    }
+;
+target datalayout = "e-m:e-p:32:32-i64:64-v128:64:128-a:0:32-n32-S64"
+
+; Function Attrs: norecurse nounwind
+define void @foo(i32* nocapture, i32* nocapture) {
+  br label %3
+
+; <label>:3:                                      ; preds = %2
+  br label %5
+
+; <label>:4:                                      ; preds = %8
+  ret void
+
+; <label>:5:                                      ; preds = %8, %3
+  %6 = phi i32 [ 0, %3 ], [ %9, %8 ]
+  %7 = getelementptr inbounds i32, i32* %1, i32 %6
+  br label %11
+
+; <label>:8:                                      ; preds = %11
+  %9 = add nuw nsw i32 %6, 1
+  %10 = icmp eq i32 %9, 500
+  br i1 %10, label %4, label %5
+
+; <label>:11:                                     ; preds = %11, %5
+  %12 = phi i32 [ 1, %5 ], [ %21, %11 ]
+  %13 = load i32, i32* %7, align 4
+  %14 = add nsw i32 %13, 1
+  store i32 %14, i32* %7, align 4
+  %15 = urem i32 %12, 250
+  %16 = getelementptr inbounds i32, i32* %0, i32 %15
+  %17 = load i32, i32* %16, align 4
+  %18 = getelementptr inbounds i32, i32* %0, i32 %12
+  %19 = load i32, i32* %18, align 4
+  %20 = add nsw i32 %19, %17
+  store i32 %20, i32* %18, align 4
+  %21 = add nuw nsw i32 %12, 1
+  %22 = icmp eq i32 %21, 1000
+  br i1 %22, label %8, label %11
+}