[Polly] [DependenceInfo] change WAR generation, Read will not block Read

[bollu]

Summary

Earlier, the call to buildFlow was:

WAR = buildFlow(Write, Read, MustWrite, Schedule).

This meant that Read could block another Read, since must-sources can
block each other.

Fixed the call to buildFlow to correctly compute Read. The resulting
code needs to do some ISL juggling to get the output we want.

Bug report: https://bugs.llvm.org/show_bug.cgi?id=32623

[bollu]

@jdoerfert , @Meinersbur : ping, review please?

[bollu]

• separate out WAR generation into a separate pure function

[bollu]

@grosser, @Meinersbur, @jdoerfert, @gareevroman : This change affects the dependence generation, so I'd like someone else to take a look at it before I check it in.

[Meinersbur]

lib/Analysis/DependenceInfo.cpp

370–371

Functions usually have a Doxygen comment (with triple slashes, brief description and @param/@return annotation)

372–402

This can be done way simpler. Suggestions:

1. Negate all coefficients of the Schedule (e.g. S[i] -> [1, i] becomes S[i] -> [-1,-i] ) and compute normal RAW dependencies on that. Order of reads and write are reversed, so you get WAR dependencies.

2. You only want dependencies of the form [Write -> Read], but you have [Write -> Read+MustWrite] (after you get rid of the MemAccess part). Just intersect with Read's domain.

return isl_union_map_intersect_domain(isl_union_map_domain_factor_domain(WAROverestimated), isl_union_map_domain(Read));

3. Iterate over all maps in the union (foreachElt) and filter out all map spaces that are not of the form [Write -> Read].

Suggestion 2+3 actually require accesses that have access-level tags (Dependences::AL_Access) to identifiy whether it is a read or a write, so it might not really be simpler.

My favorite is suggestion 1. It it easiest to understand (even the may-write part becomes obvious) and has the least computational overhead, apart from copying an entire Schedule once.

This version should be correct as well, however.

376

I like the annotation, I do these as well. Can you make the style more consistent with isl's string output?

• Always surrounded by braces
• Nested tuples surrounded by brackets (not parentheses)

Also MemoryAccess have Ids of the form Stmt_S0_Read0_MemRef_C. MemRef_C alone is an Id of a ScopArrayInfo. I am using Element[] for this purpose.

[bollu]

@Meinersbur: Would you be OK with me pushing this patch, and changing the generation to the simpler method proposed in the next patch? I would like to get correctness first.

[Meinersbur]

Yes, this is why I accepted the patch.

lib/Analysis/DependenceInfo.cpp

static __isl_give isl_union_flow *buildFlow(__isl_keep isl_union_map *Snk,
   AI = isl_union_access_info_set_schedule(AI, isl_schedule_copy(Schedule));
   auto Flow = isl_union_access_info_compute_flow(AI);
   DEBUG(if (!Flow) dbgs() << "last error: "
                           << isl_ctx_last_error(isl_schedule_get_ctx(Schedule))
                           << '\n';);
   return Flow;
 }
 
+// We need exact WAR dependences. That is, if there are
+// dependences of the form:
+// must-W2 (sink) <- must-W1 (sink) <- R (source)
+// We wish to generate *ONLY*:
+// { R -> W1 },
+// NOT:
+// { R -> W2, R -> W1 }
+//
+// However, in the case of may-writes, we do *not* wish to allow
+// may-writes to block must-writes. This makes sense, since perhaps the
+// may-write will not happen. In that case, the exact dependence will
+// be the (read -> must-write).
+// Example:
+// must-W2 (sink) <- may-W1 (sink) <- R (source)
+// We wish to generate:
+// { R-> W1, R -> W2 }
+//
+// We use the fact that may dependences are not allowed to flow
+// through a must source. That way, reads will be stopped by intermediate
+// must-writes.
+// However, may-sources may not interfere with one another. Hence, reads
+// will not block each other from generating dependences.
+//
+// Write (Sink) <- MustWrite (Must-Source) <- Read (MaySource) is
+// present, then the dependence
+//    { Write <- Read }
+// is not tracked.
+//
+// We would like to specify the Must-Write as kills, source as Read
+// and sink as Write.
+// ISL does not have the functionality currently to support "kills".
+// Use the Must-Source as a way to specify "kills".
+// The drawback is that we will have both
+//   { Write <- MustWrite, Write <- Read }
+//
+// We need to filter this to track only { Write <- Read }.
+//
+// Filtering { Write <- Read } from WAROverestimated:
+// --------------------------------------------------
+// isl_union_flow_get_full_may_dependence gives us dependences of the form
+//   WAROverestimated = { Read+MustWrite -> [Write -> MemoryAccess]}
+//
+//  We need to intersect the domain with Read to get only
+//  Read dependences.
+//    Read = { Read -> MemoryAccess }
+//
+//
+// 1. Construct:
+//   WARMemAccesses = { Read+Write -> [Read+Write -> MemoryAccess] }
+// This takes a Read+Write from WAROverestimated and maps it to the
+// corresponding wrapped memory access from WAROverestimated.
+//
+// 2. Apply WARMemAcesses to the domain of WAR Overestimated to give:
+//   WAR = { [Read+Write -> MemoryAccess] -> [Write -> MemoryAccess] }
+//
+// WAR is in a state where we can intersect with Read, since they
+// have the same structure.
+//
+// 3. Intersect this with a wrapped Read. Read is wrapped
+// to ensure the domains look the same.
+//   WAR = WAR \intersect (wrapped Read)
+//   WAR = { [Read -> MemoryAccesss] -> [Write -> MemoryAccess] }
+//
+//  4. Project out the memory access in the domain to get
+//  WAR = { Read -> Write }
+
+static isl_union_map *buildWAR(isl_union_map *Write, isl_union_map *MustWrite,
+                               isl_union_map *Read, isl_schedule *Schedule) {
+  isl_union_flow *Flow = buildFlow(Write, MustWrite, Read, Schedule);
+  auto *WAROverestimated = isl_union_flow_get_full_may_dependence(Flow);
+
+  // 1. Constructing WARMemAccesses
+  // Read+Write -> (Write -> MemAccess)
+  //
+  // Range factor of range product
+  //     { Read+Write -> MemAcesss }
+  // Domain projection
+  //     { [Read+Write -> MemAccess] -> Read+Write }
+  // Reverse
+  //     { Read+Write -> [Read+Write -> MemAccess] }
+  auto WARMemAccesses = isl_union_map_copy(WAROverestimated);
+  WARMemAccesses = isl_union_map_range_factor_range(WAROverestimated);
+  WARMemAccesses = isl_union_map_domain_map(WARMemAccesses);
+  WARMemAccesses = isl_union_map_reverse(WARMemAccesses);
+
+  // 2. Apply to get domain tagged with memory accesses
+  isl_union_map *WAR =
+      isl_union_map_apply_domain(WAROverestimated, WARMemAccesses);
+
+  // 3. Intersect with Read to extract only reads
+  auto ReadWrapped = isl_union_map_wrap(isl_union_map_copy(Read));
+  WAR = isl_union_map_intersect_domain(WAR, ReadWrapped);
+
+  // 4. Project out memory accesses to get usual style dependences
+  WAR = isl_union_map_range_factor_domain(WAR);
+  WAR = isl_union_map_domain_factor_domain(WAR);
+
+  isl_union_flow_free(Flow);
+  return WAR;
+}
+
 void Dependences::calculateDependences(Scop &S) {
   isl_union_map *Read, *MustWrite, *MayWrite, *ReductionTagMap;
   isl_schedule *Schedule;
   isl_union_set *TaggedStmtDomain;
 
   DEBUG(dbgs() << "Scop: \n" << S << "\n");
 
   collectInfo(S, Read, MustWrite, MayWrite, ReductionTagMap, TaggedStmtDomain,
if (OptAnalysisType == VALUE_BASED_ANALYSIS) {
       Flow = buildFlow(Read, MustWrite, MayWrite, Schedule);
       RAW = isl_union_flow_get_may_dependence(Flow);
       isl_union_flow_free(Flow);
 
       Flow = buildFlow(Write, MustWrite, MayWrite, Schedule);
       WAW = isl_union_flow_get_may_dependence(Flow);
       isl_union_flow_free(Flow);
 
-      // We need exact WAR dependences. That is, if there are
-      // dependences of the form:
-      // must-W2 (sink) <- must-W1 (sink) <- R (source)
-      // We wish to generate *ONLY*:
-      // { R -> W1 },
-      // NOT:
-      // { R -> W2, R -> W1 }
-      //
-      // However, in the case of may-writes, we do *not* wish to allow
-      // may-writes to block must-writes. This makes sense, since perhaps the
-      // may-write will not happen. In that case, the exact dependence will
-      // be the (read -> must-write).
-      // Example:
-      // must-W2 (sink) <- may-W1 (sink) <- R (source)
-      // We wish to generate:
-      // { R-> W1, R -> W2 }
-      //
-      //
-      // To achieve this, we use the fact that *must* dependences are not
-      // allowed to flow through the may-source.
-      // Since we set the may-source to MustWrite, we are guarenteed that
-      // only the exact ("shortest") (must-write -> read) is captured.
-      // Any number of intermediate may-writes are allowed.
-      Flow = buildFlow(Write, Read, MustWrite, Schedule);
-      WAR = isl_union_flow_get_must_dependence(Flow);
-      isl_union_flow_free(Flow);
-
+      WAR = buildWAR(Write, MustWrite, Read, Schedule);
       isl_union_map_free(Write);
       isl_schedule_free(Schedule);
     } else {
       isl_union_flow *Flow;
 
       Flow = buildFlow(Read, nullptr, Write, Schedule);
       RAW = isl_union_flow_get_may_dependence(Flow);
       isl_union_flow_free(Flow);

test/DependenceInfo/different_schedule_dimensions.ll

 ; CHECK: WAW dependences:
 ; CHECK:   { Stmt_bb3[0] -> Stmt_bb10[0] }
 ; CHECK: Reduction dependences:
 ; CHECK:   {  }
 
 ; FUNC: RAW dependences:
 ; FUNC-NEXT:   { Stmt_bb9[0] -> Stmt_bb10[0]; [Stmt_bb9[0] -> Stmt_bb9_Write0_MemRef_tmp11[]] -> [Stmt_bb10[0] -> Stmt_bb10_Read0_MemRef_tmp11[]] }
 ; FUNC-NEXT: WAR dependences:
-; FUNC-NEXT:   { Stmt_bb3[0] -> Stmt_bb10[0]; [Stmt_bb3[0] -> Stmt_bb3_Read0_MemRef_arg1[]] -> [Stmt_bb10[0] -> Stmt_bb10_Write1_MemRef_arg1[]] }
+; FUNC-NEXT:   { }
 ; FUNC-NEXT: WAW dependences:
 ; FUNC-NEXT:   { Stmt_bb3[0] -> Stmt_bb10[0]; [Stmt_bb3[0] -> Stmt_bb3_Write1_MemRef_arg1[]] -> [Stmt_bb10[0] -> Stmt_bb10_Write1_MemRef_arg1[]] }
 ; FUNC-NEXT: Reduction dependences:
 ; FUNC-NEXT:   {  }
 
 target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
 
 define void @hoge(i32 %arg, [1024 x double]* %arg1) {

test/DependenceInfo/do_pluto_matmult.ll

 ; MEMORY-NEXT: WAR dependences:
 ; MEMORY-NEXT:     { Stmt_do_body2[i0, i1, i2] -> Stmt_do_body2[i0, i1, o2] : 0 <= i0 <= 35 and 0 <= i1 <= 35 and i2 >= 0 and i2 < o2 <= 35 }
 ; MEMORY-NEXT: WAW dependences:
 ; MEMORY-NEXT:     { Stmt_do_body2[i0, i1, i2] -> Stmt_do_body2[i0, i1, o2] : 0 <= i0 <= 35 and 0 <= i1 <= 35 and i2 >= 0 and i2 < o2 <= 35 }
 
 ; FUNC-VALUE:      RAW dependences:
 ; FUNC-VALUE-NEXT:     { [Stmt_do_body2[i0, i1, i2] -> Stmt_do_body2_Write3_MemRef_C[]] -> [Stmt_do_body2[i0, i1, 1 + i2] -> Stmt_do_body2_Read0_MemRef_C[]] : 0 <= i0 <= 35 and 0 <= i1 <= 35 and 0 <= i2 <= 34; Stmt_do_body2[i0, i1, i2] -> Stmt_do_body2[i0, i1, 1 + i2] : 0 <= i0 <= 35 and 0 <= i1 <= 35 and 0 <= i2 <= 34 }
 ; FUNC-VALUE-NEXT: WAR dependences:
-; FUNC-VALUE-NEXT:     { [Stmt_do_body2[i0, i1, i2] -> Stmt_do_body2_Read0_MemRef_C[]] -> [Stmt_do_body2[i0, i1, 1 + i2] -> Stmt_do_body2_Write3_MemRef_C[]] : 0 <= i0 <= 35 and 0 <= i1 <= 35 and 0 <= i2 <= 34; Stmt_do_body2[i0, i1, i2] -> Stmt_do_body2[i0, i1, 1 + i2] : 0 <= i0 <= 35 and 0 <= i1 <= 35 and 0 <= i2 <= 34 }
+; FUNC-VALUE-NEXT:     { }
 ; FUNC-VALUE-NEXT: WAW dependences:
 ; FUNC-VALUE-NEXT:     { [Stmt_do_body2[i0, i1, i2] -> Stmt_do_body2_Write3_MemRef_C[]] -> [Stmt_do_body2[i0, i1, 1 + i2] -> Stmt_do_body2_Write3_MemRef_C[]] : 0 <= i0 <= 35 and 0 <= i1 <= 35 and 0 <= i2 <= 34; Stmt_do_body2[i0, i1, i2] -> Stmt_do_body2[i0, i1, 1 + i2] : 0 <= i0 <= 35 and 0 <= i1 <= 35 and 0 <= i2 <= 34 }
 
 ; FUNC-MEMORY:      RAW dependences:
 ; FUNC-MEMORY-NEXT:     { [Stmt_do_body2[i0, i1, i2] -> Stmt_do_body2_Write3_MemRef_C[]] -> [Stmt_do_body2[i0, i1, o2] -> Stmt_do_body2_Read0_MemRef_C[]] : 0 <= i0 <= 35 and 0 <= i1 <= 35 and i2 >= 0 and i2 < o2 <= 35; Stmt_do_body2[i0, i1, i2] -> Stmt_do_body2[i0, i1, o2] : 0 <= i0 <= 35 and 0 <= i1 <= 35 and i2 >= 0 and i2 < o2 <= 35 }
 ; FUNC-MEMORY-NEXT: WAR dependences:
 ; FUNC-MEMORY-NEXT:     { [Stmt_do_body2[i0, i1, i2] -> Stmt_do_body2_Read0_MemRef_C[]] -> [Stmt_do_body2[i0, i1, o2] -> Stmt_do_body2_Write3_MemRef_C[]] : 0 <= i0 <= 35 and 0 <= i1 <= 35 and i2 >= 0 and i2 < o2 <= 35; Stmt_do_body2[i0, i1, i2] -> Stmt_do_body2[i0, i1, o2] : 0 <= i0 <= 35 and 0 <= i1 <= 35 and i2 >= 0 and i2 < o2 <= 35 }
 ; FUNC-MEMORY-NEXT: WAW dependences:
 ; FUNC-MEMORY-NEXT:     { [Stmt_do_body2[i0, i1, i2] -> Stmt_do_body2_Write3_MemRef_C[]] -> [Stmt_do_body2[i0, i1, o2] -> Stmt_do_body2_Write3_MemRef_C[]] : 0 <= i0 <= 35 and 0 <= i1 <= 35 and i2 >= 0 and i2 < o2 <= 35; Stmt_do_body2[i0, i1, i2] -> Stmt_do_body2[i0, i1, o2] : 0 <= i0 <= 35 and 0 <= i1 <= 35 and i2 >= 0 and i2 < o2 <= 35 }

test/DependenceInfo/reduction_privatization_deps.ll

 ; RUN: opt %loadPolly -polly-dependences -analyze < %s | FileCheck %s
 ;
 ; CHECK:      RAW dependences:
 ; CHECK-NEXT:     { Stmt_S0[i0] -> Stmt_S1[o0, i0 - o0] : i0 <= 1023 and 0 <= o0 <= i0; Stmt_S1[i0, i1] -> Stmt_S2[-1 + i0 + i1] : 0 <= i0 <= 1023 and i1 >= 0 and -i0 < i1 <= 1024 - i0 and i1 <= 1023 }
 ; CHECK-NEXT: WAR dependences:
-; CHECK-NEXT:     { Stmt_S2[i0] -> Stmt_S2[1 + i0] : 0 <= i0 <= 1022; Stmt_S1[0, 0] -> Stmt_S2[0] }
+; CHECK-NEXT:     { Stmt_S2[i0] -> Stmt_S2[1 + i0] : 0 <= i0 <= 1022; Stmt_S1[i0, i1] -> Stmt_S2[i0 + i1] : i0 >= 0 and 0 <= i1 <= 1023 - i0 }
 ; CHECK-NEXT: WAW dependences:
 ; CHECK-NEXT:     { Stmt_S0[i0] -> Stmt_S1[o0, i0 - o0] : i0 <= 1023 and 0 <= o0 <= i0; Stmt_S1[i0, i1] -> Stmt_S2[i0 + i1] : i0 >= 0 and 0 <= i1 <= 1023 - i0 }
 ; CHECK-NEXT: Reduction dependences:
 ; CHECK-NEXT:     { Stmt_S1[i0, i1] -> Stmt_S1[1 + i0, -1 + i1] : 0 <= i0 <= 1022 and 0 < i1 <= 1023 }
 ;
 ;    void f(int *sum) {
 ;      for (int i = 0; i < 1024; i++)
 ; S0:    sum[i] = 0;