From f8ee915deb887055326390d58800778d1ae5853e Mon Sep 17 00:00:00 2001 From: Johannes Doerfert Date: Thu, 26 Jun 2014 18:44:14 +0000 Subject: [PATCH] Use wrapped reduction dependences This change will ease the transision to multiple reductions per statement as we can now distinguish the effects of multiple reductions in the same statement. + Wrapped reduction dependences are used to compute privatization dependences + Modified test cases to account for the change llvm-svn: 211795 --- polly/lib/Analysis/Dependences.cpp | 42 ++++++++------ .../Dependences/reduction_multiple_reductions.ll | 3 +- .../Dependences/reduction_privatization_deps.ll | 1 - ...eduction_simple_iv_debug_wrapped_dependences.ll | 65 ++++++++++++++-------- 4 files changed, 67 insertions(+), 44 deletions(-) diff --git a/polly/lib/Analysis/Dependences.cpp b/polly/lib/Analysis/Dependences.cpp index bcdcb93..37be06c 100644 --- a/polly/lib/Analysis/Dependences.cpp +++ b/polly/lib/Analysis/Dependences.cpp @@ -284,22 +284,6 @@ void Dependences::calculateDependences(Scop &S) { isl_union_map_domain(StmtSchedule)); DEBUG(dbgs() << "Wrapped Dependences:\n"; printScop(dbgs()); dbgs() << "\n"); - RAW = isl_union_map_zip(RAW); - WAW = isl_union_map_zip(WAW); - WAR = isl_union_map_zip(WAR); - - DEBUG(dbgs() << "Zipped Dependences:\n"; printScop(dbgs()); dbgs() << "\n"); - - RAW = isl_union_map_union(isl_union_set_unwrap(isl_union_map_domain(RAW)), - STMT_RAW); - WAW = isl_union_map_union(isl_union_set_unwrap(isl_union_map_domain(WAW)), - STMT_WAW); - WAR = isl_union_map_union(isl_union_set_unwrap(isl_union_map_domain(WAR)), - STMT_WAR); - - DEBUG(dbgs() << "Unwrapped Dependences:\n"; printScop(dbgs()); - dbgs() << "\n"); - // To handle reduction dependences we proceed as follows: // 1) Aggregate all possible reduction dependences, namely all self // dependences on reduction like statements. @@ -320,9 +304,9 @@ void Dependences::calculateDependences(Scop &S) { for (MemoryAccess *MA : *Stmt) { if (!MA->isReductionLike()) continue; - isl_set *AccDom = isl_map_domain(MA->getAccessRelation()); + isl_set *AccDomW = isl_map_wrap(MA->getAccessRelation()); isl_map *Identity = - isl_map_from_domain_and_range(isl_set_copy(AccDom), AccDom); + isl_map_from_domain_and_range(isl_set_copy(AccDomW), AccDomW); RED = isl_union_map_add_map(RED, Identity); break; } @@ -342,6 +326,28 @@ void Dependences::calculateDependences(Scop &S) { addPrivatizationDependences(); } + DEBUG(dbgs() << "Final Wrapped Dependences:\n"; printScop(dbgs()); + dbgs() << "\n"); + + RAW = isl_union_map_zip(RAW); + WAW = isl_union_map_zip(WAW); + WAR = isl_union_map_zip(WAR); + RED = isl_union_map_zip(RED); + + DEBUG(dbgs() << "Zipped Dependences:\n"; printScop(dbgs()); dbgs() << "\n"); + + RAW = isl_union_set_unwrap(isl_union_map_domain(RAW)); + WAW = isl_union_set_unwrap(isl_union_map_domain(WAW)); + WAR = isl_union_set_unwrap(isl_union_map_domain(WAR)); + RED = isl_union_set_unwrap(isl_union_map_domain(RED)); + + DEBUG(dbgs() << "Unwrapped Dependences:\n"; printScop(dbgs()); + dbgs() << "\n"); + + RAW = isl_union_map_union(RAW, STMT_RAW); + WAW = isl_union_map_union(WAW, STMT_WAW); + WAR = isl_union_map_union(WAR, STMT_WAR); + RAW = isl_union_map_coalesce(RAW); WAW = isl_union_map_coalesce(WAW); WAR = isl_union_map_coalesce(WAR); diff --git a/polly/test/Dependences/reduction_multiple_reductions.ll b/polly/test/Dependences/reduction_multiple_reductions.ll index 68bb81a..461f9e4 100644 --- a/polly/test/Dependences/reduction_multiple_reductions.ll +++ b/polly/test/Dependences/reduction_multiple_reductions.ll @@ -9,7 +9,8 @@ ; CHECK: WAW dependences: ; CHECK: { } ; CHECK: Reduction dependences: -; CHECK: { Stmt_if_then[i0] -> Stmt_if_then[1 + i0] : i0 <= 510 and i0 >= 0; Stmt_if_else[i0] -> Stmt_if_else[1 + i0] : i0 <= 1022 and i0 >= 512 } +; CHECK-DAG: Stmt_if_then[i0] -> Stmt_if_then[1 + i0] : i0 <= 510 and i0 >= 0 +; CHECK-DAG: Stmt_if_else[i0] -> Stmt_if_else[1 + i0] : i0 <= 1022 and i0 >= 512 ; ; void f(int *restrict sum, int *restrict prod) { ; for (int i = 0; i < 1024; i++) diff --git a/polly/test/Dependences/reduction_privatization_deps.ll b/polly/test/Dependences/reduction_privatization_deps.ll index e733a3d..a4f0895 100644 --- a/polly/test/Dependences/reduction_privatization_deps.ll +++ b/polly/test/Dependences/reduction_privatization_deps.ll @@ -24,7 +24,6 @@ ; for (int i = 0; i < 1024; i++) ; S2: sum[i] = sum[i + 1] * 3; ; } -; target datalayout = "e-m:e-p:32:32-i64:64-v128:64:128-n32-S64" define void @f(i32* %sum) { diff --git a/polly/test/Dependences/reduction_simple_iv_debug_wrapped_dependences.ll b/polly/test/Dependences/reduction_simple_iv_debug_wrapped_dependences.ll index ae46134..2982f9e 100644 --- a/polly/test/Dependences/reduction_simple_iv_debug_wrapped_dependences.ll +++ b/polly/test/Dependences/reduction_simple_iv_debug_wrapped_dependences.ll @@ -6,32 +6,49 @@ ; CHECK: Write: { [Stmt_for_cond[i0] -> MemRef_sum[0]] -> MemRef_sum[0] : i0 >= 0 and i0 <= 100 } ; CHECK: Schedule: { Stmt_for_cond[i0] -> scattering[0, i0, 0]; [Stmt_for_cond[i0] -> MemRef_sum[0]] -> scattering[0, i0, 0] : i0 <= 100 and i0 >= 0 } ; CHECK: Wrapped Dependences: -; CHECK: RAW dependences: -; CHECK: { [Stmt_for_cond[i0] -> MemRef_sum[0]] -> [Stmt_for_cond[1 + i0] -> MemRef_sum[0]] : i0 >= 0 and i0 <= 99 } -; CHECK: WAR dependences: -; CHECK: { } -; CHECK: WAW dependences: -; CHECK: { [Stmt_for_cond[i0] -> MemRef_sum[0]] -> [Stmt_for_cond[1 + i0] -> MemRef_sum[0]] : i0 >= 0 and i0 <= 99 } -; CHECK: Reduction dependences: -; CHECK: n/a +; CHECK: RAW dependences: +; CHECK: { [Stmt_for_cond[i0] -> MemRef_sum[0]] -> [Stmt_for_cond[1 + i0] -> MemRef_sum[0]] : i0 >= 0 and i0 <= 99 } +; CHECK: WAR dependences: +; CHECK: { } +; CHECK: WAW dependences: +; CHECK: { [Stmt_for_cond[i0] -> MemRef_sum[0]] -> [Stmt_for_cond[1 + i0] -> MemRef_sum[0]] : i0 >= 0 and i0 <= 99 } +; CHECK: Reduction dependences: +; CHECK: n/a +; CHECK: Final Wrapped Dependences: +; CHECK: RAW dependences: +; CHECK: { } +; CHECK: WAR dependences: +; CHECK: { } +; CHECK: WAW dependences: +; CHECK: { } +; CHECK: Reduction dependences: +; CHECK: { [Stmt_for_cond[i0] -> MemRef_sum[0]] -> [Stmt_for_cond[1 + i0] -> MemRef_sum[0]] : i0 <= 99 and i0 >= 0 } ; CHECK: Zipped Dependences: -; CHECK: RAW dependences: -; CHECK: { [Stmt_for_cond[i0] -> Stmt_for_cond[1 + i0]] -> [MemRef_sum[0] -> MemRef_sum[0]] : i0 >= 0 and i0 <= 99 } -; CHECK: WAR dependences: -; CHECK: { } -; CHECK: WAW dependences: -; CHECK: { [Stmt_for_cond[i0] -> Stmt_for_cond[1 + i0]] -> [MemRef_sum[0] -> MemRef_sum[0]] : i0 >= 0 and i0 <= 99 } -; CHECK: Reduction dependences: -; CHECK: n/a +; CHECK: RAW dependences: +; CHECK: { } +; CHECK: WAR dependences: +; CHECK: { } +; CHECK: WAW dependences: +; CHECK: { } +; CHECK: Reduction dependences: +; CHECK: { [Stmt_for_cond[i0] -> Stmt_for_cond[1 + i0]] -> [MemRef_sum[0] -> MemRef_sum[0]] : i0 <= 99 and i0 >= 0 } ; CHECK: Unwrapped Dependences: -; CHECK: RAW dependences: -; CHECK: { Stmt_for_cond[i0] -> Stmt_for_cond[1 + i0] : i0 >= 0 and i0 <= 99 } -; CHECK: WAR dependences: -; CHECK: { } -; CHECK: WAW dependences: -; CHECK: { Stmt_for_cond[i0] -> Stmt_for_cond[1 + i0] : i0 >= 0 and i0 <= 99 } -; CHECK: Reduction dependences: -; CHECK: n/a +; CHECK: RAW dependences: +; CHECK: { } +; CHECK: WAR dependences: +; CHECK: { } +; CHECK: WAW dependences: +; CHECK: { } +; CHECK: Reduction dependences: +; CHECK: { Stmt_for_cond[i0] -> Stmt_for_cond[1 + i0] : i0 <= 99 and i0 >= 0 } +; CHECK: RAW dependences: +; CHECK: { } +; CHECK: WAR dependences: +; CHECK: { } +; CHECK: WAW dependences: +; CHECK: { } +; CHECK: Reduction dependences: +; CHECK: { Stmt_for_cond[i0] -> Stmt_for_cond[1 + i0] : i0 <= 99 and i0 >= 0 } ; ; void f(int* sum) { ; for (int i = 0; i <= 100; i++) -- 2.7.4