Index: polly/trunk/lib/Analysis/DependenceInfo.cpp =================================================================== --- polly/trunk/lib/Analysis/DependenceInfo.cpp +++ polly/trunk/lib/Analysis/DependenceInfo.cpp @@ -288,6 +288,7 @@ static __isl_give isl_union_flow *buildFlow(__isl_keep isl_union_map *Snk, __isl_keep isl_union_map *Src, __isl_keep isl_union_map *MaySrc, + __isl_keep isl_union_map *Kill, __isl_keep isl_schedule *Schedule) { isl_union_access_info *AI; @@ -296,6 +297,8 @@ AI = isl_union_access_info_set_may_source(AI, isl_union_map_copy(MaySrc)); if (Src) AI = isl_union_access_info_set_must_source(AI, isl_union_map_copy(Src)); + if (Kill) + AI = isl_union_access_info_set_kill(AI, isl_union_map_copy(Kill)); AI = isl_union_access_info_set_schedule(AI, isl_schedule_copy(Schedule)); auto Flow = isl_union_access_info_compute_flow(AI); LLVM_DEBUG(if (!Flow) dbgs() @@ -305,106 +308,6 @@ 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_range_factor_range(isl_union_map_copy(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; @@ -530,44 +433,43 @@ // } // } - isl_union_flow *Flow = buildFlow(Write, Write, Read, Schedule); + isl_union_flow *Flow = buildFlow(Write, Write, Read, nullptr, Schedule); StrictWAW = isl_union_flow_get_must_dependence(Flow); isl_union_flow_free(Flow); if (OptAnalysisType == VALUE_BASED_ANALYSIS) { - Flow = buildFlow(Read, MustWrite, MayWrite, Schedule); + Flow = buildFlow(Read, MustWrite, MayWrite, nullptr, Schedule); RAW = isl_union_flow_get_may_dependence(Flow); isl_union_flow_free(Flow); - Flow = buildFlow(Write, MustWrite, MayWrite, Schedule); + Flow = buildFlow(Write, MustWrite, MayWrite, nullptr, Schedule); WAW = isl_union_flow_get_may_dependence(Flow); isl_union_flow_free(Flow); - WAR = buildWAR(Write, MustWrite, Read, Schedule); - isl_union_map_free(Write); - isl_schedule_free(Schedule); + // ISL now supports "kills" in approximate dataflow analysis, we can + // specify the MustWrite as kills, Read as source and Write as sink. + Flow = buildFlow(Write, nullptr, Read, MustWrite, Schedule); + WAR = isl_union_flow_get_may_dependence(Flow); + isl_union_flow_free(Flow); } else { - isl_union_flow *Flow; - - Flow = buildFlow(Read, nullptr, Write, Schedule); + Flow = buildFlow(Read, nullptr, Write, nullptr, Schedule); RAW = isl_union_flow_get_may_dependence(Flow); isl_union_flow_free(Flow); - Flow = buildFlow(Write, nullptr, Read, Schedule); + Flow = buildFlow(Write, nullptr, Read, nullptr, Schedule); WAR = isl_union_flow_get_may_dependence(Flow); isl_union_flow_free(Flow); - Flow = buildFlow(Write, nullptr, Write, Schedule); + Flow = buildFlow(Write, nullptr, Write, nullptr, Schedule); WAW = isl_union_flow_get_may_dependence(Flow); isl_union_flow_free(Flow); - - isl_union_map_free(Write); - isl_schedule_free(Schedule); } + isl_union_map_free(Write); isl_union_map_free(MustWrite); isl_union_map_free(MayWrite); isl_union_map_free(Read); + isl_schedule_free(Schedule); RAW = isl_union_map_coalesce(RAW); WAW = isl_union_map_coalesce(WAW);