From 729377f06303485eea7c2e031af4eb7f13c0cb96 Mon Sep 17 00:00:00 2001 From: Siddharth Bhat Date: Mon, 24 Apr 2017 22:23:12 +0000 Subject: [PATCH] [Polly] [DependenceInfo] change WAR generation, Read will not block Read 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 Reviewers: Meinersbur Tags: #polly Differential Revision: https://reviews.llvm.org/D32011 llvm-svn: 301266 --- polly/lib/Analysis/DependenceInfo.cpp | 128 ++++++++++++++++----- .../different_schedule_dimensions.ll | 2 +- polly/test/DependenceInfo/do_pluto_matmult.ll | 2 +- .../DependenceInfo/reduction_privatization_deps.ll | 2 +- 4 files changed, 104 insertions(+), 30 deletions(-) diff --git a/polly/lib/Analysis/DependenceInfo.cpp b/polly/lib/Analysis/DependenceInfo.cpp index cec4ce7..8aa9f8d 100644 --- a/polly/lib/Analysis/DependenceInfo.cpp +++ b/polly/lib/Analysis/DependenceInfo.cpp @@ -301,6 +301,106 @@ static __isl_give isl_union_flow *buildFlow(__isl_keep isl_union_map *Snk, return Flow; } +/// Compute exact WAR dependences +/// 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 + // 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; @@ -439,33 +539,7 @@ void Dependences::calculateDependences(Scop &S) { 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 { diff --git a/polly/test/DependenceInfo/different_schedule_dimensions.ll b/polly/test/DependenceInfo/different_schedule_dimensions.ll index 42b6ba1..81cf18a 100644 --- a/polly/test/DependenceInfo/different_schedule_dimensions.ll +++ b/polly/test/DependenceInfo/different_schedule_dimensions.ll @@ -15,7 +15,7 @@ ; 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: diff --git a/polly/test/DependenceInfo/do_pluto_matmult.ll b/polly/test/DependenceInfo/do_pluto_matmult.ll index 8a436e5..66a05f9 100644 --- a/polly/test/DependenceInfo/do_pluto_matmult.ll +++ b/polly/test/DependenceInfo/do_pluto_matmult.ll @@ -83,7 +83,7 @@ do.end45: ; preds = %do.cond42 ; 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 } diff --git a/polly/test/DependenceInfo/reduction_privatization_deps.ll b/polly/test/DependenceInfo/reduction_privatization_deps.ll index 422f213..e51357a 100644 --- a/polly/test/DependenceInfo/reduction_privatization_deps.ll +++ b/polly/test/DependenceInfo/reduction_privatization_deps.ll @@ -3,7 +3,7 @@ ; 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: -- 2.7.4