865 lines · cpp
1//===- DependenceInfo.cpp - Calculate dependency information for a Scop. --===//2//3// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.4// See https://llvm.org/LICENSE.txt for license information.5// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception6//7//===----------------------------------------------------------------------===//8//9// Calculate the data dependency relations for a Scop using ISL.10//11// The integer set library (ISL) from Sven, has a integrated dependency analysis12// to calculate data dependences. This pass takes advantage of this and13// calculate those dependences a Scop.14//15// The dependences in this pass are exact in terms that for a specific read16// statement instance only the last write statement instance is returned. In17// case of may writes a set of possible write instances is returned. This18// analysis will never produce redundant dependences.19//20//===----------------------------------------------------------------------===//21//22#include "polly/DependenceInfo.h"23#include "polly/Options.h"24#include "polly/ScopInfo.h"25#include "polly/Support/GICHelper.h"26#include "polly/Support/ISLTools.h"27#include "llvm/ADT/Sequence.h"28#include "llvm/Support/Debug.h"29#include "isl/aff.h"30#include "isl/ctx.h"31#include "isl/flow.h"32#include "isl/map.h"33#include "isl/schedule.h"34#include "isl/set.h"35#include "isl/union_map.h"36#include "isl/union_set.h"37 38using namespace polly;39using namespace llvm;40 41#include "polly/Support/PollyDebug.h"42#define DEBUG_TYPE "polly-dependence"43 44namespace polly {45Dependences::AnalysisLevel OptAnalysisLevel;46}47 48static cl::opt<int> OptComputeOut(49 "polly-dependences-computeout",50 cl::desc("Bound the dependence analysis by a maximal amount of "51 "computational steps (0 means no bound)"),52 cl::Hidden, cl::init(500000), cl::cat(PollyCategory));53 54static cl::opt<bool>55 LegalityCheckDisabled("disable-polly-legality",56 cl::desc("Disable polly legality check"), cl::Hidden,57 cl::cat(PollyCategory));58 59static cl::opt<bool>60 UseReductions("polly-dependences-use-reductions",61 cl::desc("Exploit reductions in dependence analysis"),62 cl::Hidden, cl::init(true), cl::cat(PollyCategory));63 64enum AnalysisType { VALUE_BASED_ANALYSIS, MEMORY_BASED_ANALYSIS };65 66static cl::opt<enum AnalysisType> OptAnalysisType(67 "polly-dependences-analysis-type",68 cl::desc("The kind of dependence analysis to use"),69 cl::values(clEnumValN(VALUE_BASED_ANALYSIS, "value-based",70 "Exact dependences without transitive dependences"),71 clEnumValN(MEMORY_BASED_ANALYSIS, "memory-based",72 "Overapproximation of dependences")),73 cl::Hidden, cl::init(VALUE_BASED_ANALYSIS), cl::cat(PollyCategory));74 75static cl::opt<Dependences::AnalysisLevel, true> XOptAnalysisLevel(76 "polly-dependences-analysis-level",77 cl::desc("The level of dependence analysis"),78 cl::location(OptAnalysisLevel),79 cl::values(clEnumValN(Dependences::AL_Statement, "statement-wise",80 "Statement-level analysis"),81 clEnumValN(Dependences::AL_Reference, "reference-wise",82 "Memory reference level analysis that distinguish"83 " accessed references in the same statement"),84 clEnumValN(Dependences::AL_Access, "access-wise",85 "Memory reference level analysis that distinguish"86 " access instructions in the same statement")),87 cl::Hidden, cl::init(Dependences::AL_Statement), cl::cat(PollyCategory));88 89//===----------------------------------------------------------------------===//90 91/// Tag the @p Relation domain with @p TagId92static __isl_give isl_map *tag(__isl_take isl_map *Relation,93 __isl_take isl_id *TagId) {94 isl_space *Space = isl_map_get_space(Relation);95 Space = isl_space_drop_dims(Space, isl_dim_out, 0,96 isl_map_dim(Relation, isl_dim_out));97 Space = isl_space_set_tuple_id(Space, isl_dim_out, TagId);98 isl_multi_aff *Tag = isl_multi_aff_domain_map(Space);99 Relation = isl_map_preimage_domain_multi_aff(Relation, Tag);100 return Relation;101}102 103/// Tag the @p Relation domain with either MA->getArrayId() or104/// MA->getId() based on @p TagLevel105static __isl_give isl_map *tag(__isl_take isl_map *Relation, MemoryAccess *MA,106 Dependences::AnalysisLevel TagLevel) {107 if (TagLevel == Dependences::AL_Reference)108 return tag(Relation, MA->getArrayId().release());109 110 if (TagLevel == Dependences::AL_Access)111 return tag(Relation, MA->getId().release());112 113 // No need to tag at the statement level.114 return Relation;115}116 117/// Collect information about the SCoP @p S.118static void collectInfo(Scop &S, isl_union_map *&Read,119 isl_union_map *&MustWrite, isl_union_map *&MayWrite,120 isl_union_map *&ReductionTagMap,121 isl_union_set *&TaggedStmtDomain,122 Dependences::AnalysisLevel Level) {123 isl_space *Space = S.getParamSpace().release();124 Read = isl_union_map_empty(isl_space_copy(Space));125 MustWrite = isl_union_map_empty(isl_space_copy(Space));126 MayWrite = isl_union_map_empty(isl_space_copy(Space));127 ReductionTagMap = isl_union_map_empty(isl_space_copy(Space));128 isl_union_map *StmtSchedule = isl_union_map_empty(Space);129 130 SmallPtrSet<const ScopArrayInfo *, 8> ReductionArrays;131 if (UseReductions)132 for (ScopStmt &Stmt : S)133 for (MemoryAccess *MA : Stmt)134 if (MA->isReductionLike())135 ReductionArrays.insert(MA->getScopArrayInfo());136 137 for (ScopStmt &Stmt : S) {138 for (MemoryAccess *MA : Stmt) {139 isl_set *domcp = Stmt.getDomain().release();140 isl_map *accdom = MA->getAccessRelation().release();141 142 accdom = isl_map_intersect_domain(accdom, domcp);143 144 if (ReductionArrays.count(MA->getScopArrayInfo())) {145 // Wrap the access domain and adjust the schedule accordingly.146 //147 // An access domain like148 // Stmt[i0, i1] -> MemAcc_A[i0 + i1]149 // will be transformed into150 // [Stmt[i0, i1] -> MemAcc_A[i0 + i1]] -> MemAcc_A[i0 + i1]151 //152 // We collect all the access domains in the ReductionTagMap.153 // This is used in Dependences::calculateDependences to create154 // a tagged Schedule tree.155 156 ReductionTagMap =157 isl_union_map_add_map(ReductionTagMap, isl_map_copy(accdom));158 accdom = isl_map_range_map(accdom);159 } else {160 accdom = tag(accdom, MA, Level);161 if (Level > Dependences::AL_Statement) {162 isl_map *StmtScheduleMap = Stmt.getSchedule().release();163 assert(StmtScheduleMap &&164 "Schedules that contain extension nodes require special "165 "handling.");166 isl_map *Schedule = tag(StmtScheduleMap, MA, Level);167 StmtSchedule = isl_union_map_add_map(StmtSchedule, Schedule);168 }169 }170 171 if (MA->isRead())172 Read = isl_union_map_add_map(Read, accdom);173 else if (MA->isMayWrite())174 MayWrite = isl_union_map_add_map(MayWrite, accdom);175 else176 MustWrite = isl_union_map_add_map(MustWrite, accdom);177 }178 179 if (!ReductionArrays.empty() && Level == Dependences::AL_Statement)180 StmtSchedule =181 isl_union_map_add_map(StmtSchedule, Stmt.getSchedule().release());182 }183 184 StmtSchedule = isl_union_map_intersect_params(185 StmtSchedule, S.getAssumedContext().release());186 TaggedStmtDomain = isl_union_map_domain(StmtSchedule);187 188 ReductionTagMap = isl_union_map_coalesce(ReductionTagMap);189 Read = isl_union_map_coalesce(Read);190 MustWrite = isl_union_map_coalesce(MustWrite);191 MayWrite = isl_union_map_coalesce(MayWrite);192}193 194/// Fix all dimension of @p Zero to 0 and add it to @p user195static void fixSetToZero(isl::set Zero, isl::union_set *User) {196 for (auto i : rangeIslSize(0, Zero.tuple_dim()))197 Zero = Zero.fix_si(isl::dim::set, i, 0);198 *User = User->unite(Zero);199}200 201/// Compute the privatization dependences for a given dependency @p Map202///203/// Privatization dependences are widened original dependences which originate204/// or end in a reduction access. To compute them we apply the transitive close205/// of the reduction dependences (which maps each iteration of a reduction206/// statement to all following ones) on the RAW/WAR/WAW dependences. The207/// dependences which start or end at a reduction statement will be extended to208/// depend on all following reduction statement iterations as well.209/// Note: "Following" here means according to the reduction dependences.210///211/// For the input:212///213/// S0: *sum = 0;214/// for (int i = 0; i < 1024; i++)215/// S1: *sum += i;216/// S2: *sum = *sum * 3;217///218/// we have the following dependences before we add privatization dependences:219///220/// RAW:221/// { S0[] -> S1[0]; S1[1023] -> S2[] }222/// WAR:223/// { }224/// WAW:225/// { S0[] -> S1[0]; S1[1024] -> S2[] }226/// RED:227/// { S1[i0] -> S1[1 + i0] : i0 >= 0 and i0 <= 1022 }228///229/// and afterwards:230///231/// RAW:232/// { S0[] -> S1[i0] : i0 >= 0 and i0 <= 1023;233/// S1[i0] -> S2[] : i0 >= 0 and i0 <= 1023}234/// WAR:235/// { }236/// WAW:237/// { S0[] -> S1[i0] : i0 >= 0 and i0 <= 1023;238/// S1[i0] -> S2[] : i0 >= 0 and i0 <= 1023}239/// RED:240/// { S1[i0] -> S1[1 + i0] : i0 >= 0 and i0 <= 1022 }241///242/// Note: This function also computes the (reverse) transitive closure of the243/// reduction dependences.244void Dependences::addPrivatizationDependences() {245 isl_union_map *PrivRAW, *PrivWAW, *PrivWAR;246 247 // The transitive closure might be over approximated, thus could lead to248 // dependency cycles in the privatization dependences. To make sure this249 // will not happen we remove all negative dependences after we computed250 // the transitive closure.251 TC_RED = isl_union_map_transitive_closure(isl_union_map_copy(RED), nullptr);252 253 // FIXME: Apply the current schedule instead of assuming the identity schedule254 // here. The current approach is only valid as long as we compute the255 // dependences only with the initial (identity schedule). Any other256 // schedule could change "the direction of the backward dependences" we257 // want to eliminate here.258 isl_union_set *UDeltas = isl_union_map_deltas(isl_union_map_copy(TC_RED));259 isl_union_set *Universe = isl_union_set_universe(isl_union_set_copy(UDeltas));260 isl::union_set Zero =261 isl::manage(isl_union_set_empty(isl_union_set_get_space(Universe)));262 263 for (isl::set Set : isl::manage_copy(Universe).get_set_list())264 fixSetToZero(Set, &Zero);265 266 isl_union_map *NonPositive =267 isl_union_set_lex_le_union_set(UDeltas, Zero.release());268 269 TC_RED = isl_union_map_subtract(TC_RED, NonPositive);270 271 TC_RED = isl_union_map_union(272 TC_RED, isl_union_map_reverse(isl_union_map_copy(TC_RED)));273 TC_RED = isl_union_map_coalesce(TC_RED);274 275 isl_union_map **Maps[] = {&RAW, &WAW, &WAR};276 isl_union_map **PrivMaps[] = {&PrivRAW, &PrivWAW, &PrivWAR};277 for (unsigned u = 0; u < 3; u++) {278 isl_union_map **Map = Maps[u], **PrivMap = PrivMaps[u];279 280 *PrivMap = isl_union_map_apply_range(isl_union_map_copy(*Map),281 isl_union_map_copy(TC_RED));282 *PrivMap = isl_union_map_union(283 *PrivMap, isl_union_map_apply_range(isl_union_map_copy(TC_RED),284 isl_union_map_copy(*Map)));285 286 *Map = isl_union_map_union(*Map, *PrivMap);287 }288 289 isl_union_set_free(Universe);290}291 292static __isl_give isl_union_flow *buildFlow(__isl_keep isl_union_map *Snk,293 __isl_keep isl_union_map *Src,294 __isl_keep isl_union_map *MaySrc,295 __isl_keep isl_union_map *Kill,296 __isl_keep isl_schedule *Schedule) {297 isl_union_access_info *AI;298 299 AI = isl_union_access_info_from_sink(isl_union_map_copy(Snk));300 if (MaySrc)301 AI = isl_union_access_info_set_may_source(AI, isl_union_map_copy(MaySrc));302 if (Src)303 AI = isl_union_access_info_set_must_source(AI, isl_union_map_copy(Src));304 if (Kill)305 AI = isl_union_access_info_set_kill(AI, isl_union_map_copy(Kill));306 AI = isl_union_access_info_set_schedule(AI, isl_schedule_copy(Schedule));307 auto Flow = isl_union_access_info_compute_flow(AI);308 POLLY_DEBUG(if (!Flow) dbgs()309 << "last error: "310 << isl_ctx_last_error(isl_schedule_get_ctx(Schedule))311 << '\n';);312 return Flow;313}314 315void Dependences::calculateDependences(Scop &S) {316 isl_union_map *Read, *MustWrite, *MayWrite, *ReductionTagMap;317 isl_schedule *Schedule;318 isl_union_set *TaggedStmtDomain;319 320 POLLY_DEBUG(dbgs() << "Scop: \n" << S << "\n");321 322 collectInfo(S, Read, MustWrite, MayWrite, ReductionTagMap, TaggedStmtDomain,323 Level);324 325 bool HasReductions = !isl_union_map_is_empty(ReductionTagMap);326 327 POLLY_DEBUG(dbgs() << "Read: " << Read << '\n';328 dbgs() << "MustWrite: " << MustWrite << '\n';329 dbgs() << "MayWrite: " << MayWrite << '\n';330 dbgs() << "ReductionTagMap: " << ReductionTagMap << '\n';331 dbgs() << "TaggedStmtDomain: " << TaggedStmtDomain << '\n';);332 333 Schedule = S.getScheduleTree().release();334 335 if (!HasReductions) {336 isl_union_map_free(ReductionTagMap);337 // Tag the schedule tree if we want fine-grain dependence info338 if (Level > AL_Statement) {339 auto TaggedMap =340 isl_union_set_unwrap(isl_union_set_copy(TaggedStmtDomain));341 auto Tags = isl_union_map_domain_map_union_pw_multi_aff(TaggedMap);342 Schedule = isl_schedule_pullback_union_pw_multi_aff(Schedule, Tags);343 }344 } else {345 isl_union_map *IdentityMap;346 isl_union_pw_multi_aff *ReductionTags, *IdentityTags, *Tags;347 348 // Extract Reduction tags from the combined access domains in the given349 // SCoP. The result is a map that maps each tagged element in the domain to350 // the memory location it accesses. ReductionTags = {[Stmt[i] ->351 // Array[f(i)]] -> Stmt[i] }352 ReductionTags =353 isl_union_map_domain_map_union_pw_multi_aff(ReductionTagMap);354 355 // Compute an identity map from each statement in domain to itself.356 // IdentityTags = { [Stmt[i] -> Stmt[i] }357 IdentityMap = isl_union_set_identity(isl_union_set_copy(TaggedStmtDomain));358 IdentityTags = isl_union_pw_multi_aff_from_union_map(IdentityMap);359 360 Tags = isl_union_pw_multi_aff_union_add(ReductionTags, IdentityTags);361 362 // By pulling back Tags from Schedule, we have a schedule tree that can363 // be used to compute normal dependences, as well as 'tagged' reduction364 // dependences.365 Schedule = isl_schedule_pullback_union_pw_multi_aff(Schedule, Tags);366 }367 368 POLLY_DEBUG(dbgs() << "Read: " << Read << "\n";369 dbgs() << "MustWrite: " << MustWrite << "\n";370 dbgs() << "MayWrite: " << MayWrite << "\n";371 dbgs() << "Schedule: " << Schedule << "\n");372 373 isl_union_map *StrictWAW = nullptr;374 {375 IslMaxOperationsGuard MaxOpGuard(IslCtx.get(), OptComputeOut);376 377 RAW = WAW = WAR = RED = nullptr;378 isl_union_map *Write = isl_union_map_union(isl_union_map_copy(MustWrite),379 isl_union_map_copy(MayWrite));380 381 // We are interested in detecting reductions that do not have intermediate382 // computations that are captured by other statements.383 //384 // Example:385 // void f(int *A, int *B) {386 // for(int i = 0; i <= 100; i++) {387 //388 // *-WAR (S0[i] -> S0[i + 1] 0 <= i <= 100)------------*389 // | |390 // *-WAW (S0[i] -> S0[i + 1] 0 <= i <= 100)------------*391 // | |392 // v |393 // S0: *A += i; >------------------*-----------------------*394 // |395 // if (i >= 98) { WAR (S0[i] -> S1[i]) 98 <= i <= 100396 // |397 // S1: *B = *A; <--------------*398 // }399 // }400 // }401 //402 // S0[0 <= i <= 100] has a reduction. However, the values in403 // S0[98 <= i <= 100] is captured in S1[98 <= i <= 100].404 // Since we allow free reordering on our reduction dependences, we need to405 // remove all instances of a reduction statement that have data dependences406 // originating from them.407 // In the case of the example, we need to remove S0[98 <= i <= 100] from408 // our reduction dependences.409 //410 // When we build up the WAW dependences that are used to detect reductions,411 // we consider only **Writes that have no intermediate Reads**.412 //413 // `isl_union_flow_get_must_dependence` gives us dependences of the form:414 // (sink <- must_source).415 //416 // It *will not give* dependences of the form:417 // 1. (sink <- ... <- may_source <- ... <- must_source)418 // 2. (sink <- ... <- must_source <- ... <- must_source)419 //420 // For a detailed reference on ISL's flow analysis, see:421 // "Presburger Formulas and Polyhedral Compilation" - Approximate Dataflow422 // Analysis.423 //424 // Since we set "Write" as a must-source, "Read" as a may-source, and ask425 // for must dependences, we get all Writes to Writes that **do not flow426 // through a Read**.427 //428 // ScopInfo::checkForReductions makes sure that if something captures429 // the reduction variable in the same basic block, then it is rejected430 // before it is even handed here. This makes sure that there is exactly431 // one read and one write to a reduction variable in a Statement.432 // Example:433 // void f(int *sum, int A[N], int B[N]) {434 // for (int i = 0; i < N; i++) {435 // *sum += A[i]; < the store and the load is not tagged as a436 // B[i] = *sum; < reduction-like access due to the overlap.437 // }438 // }439 440 isl_union_flow *Flow = buildFlow(Write, Write, Read, nullptr, Schedule);441 StrictWAW = isl_union_flow_get_must_dependence(Flow);442 isl_union_flow_free(Flow);443 444 if (OptAnalysisType == VALUE_BASED_ANALYSIS) {445 Flow = buildFlow(Read, MustWrite, MayWrite, nullptr, Schedule);446 RAW = isl_union_flow_get_may_dependence(Flow);447 isl_union_flow_free(Flow);448 449 Flow = buildFlow(Write, MustWrite, MayWrite, nullptr, Schedule);450 WAW = isl_union_flow_get_may_dependence(Flow);451 isl_union_flow_free(Flow);452 453 // ISL now supports "kills" in approximate dataflow analysis, we can454 // specify the MustWrite as kills, Read as source and Write as sink.455 Flow = buildFlow(Write, nullptr, Read, MustWrite, Schedule);456 WAR = isl_union_flow_get_may_dependence(Flow);457 isl_union_flow_free(Flow);458 } else {459 Flow = buildFlow(Read, nullptr, Write, nullptr, Schedule);460 RAW = isl_union_flow_get_may_dependence(Flow);461 isl_union_flow_free(Flow);462 463 Flow = buildFlow(Write, nullptr, Read, nullptr, Schedule);464 WAR = isl_union_flow_get_may_dependence(Flow);465 isl_union_flow_free(Flow);466 467 Flow = buildFlow(Write, nullptr, Write, nullptr, Schedule);468 WAW = isl_union_flow_get_may_dependence(Flow);469 isl_union_flow_free(Flow);470 }471 472 isl_union_map_free(Write);473 isl_union_map_free(MustWrite);474 isl_union_map_free(MayWrite);475 isl_union_map_free(Read);476 isl_schedule_free(Schedule);477 478 RAW = isl_union_map_coalesce(RAW);479 WAW = isl_union_map_coalesce(WAW);480 WAR = isl_union_map_coalesce(WAR);481 482 // End of max_operations scope.483 }484 485 if (isl_ctx_last_error(IslCtx.get()) == isl_error_quota) {486 isl_union_map_free(RAW);487 isl_union_map_free(WAW);488 isl_union_map_free(WAR);489 isl_union_map_free(StrictWAW);490 RAW = WAW = WAR = StrictWAW = nullptr;491 isl_ctx_reset_error(IslCtx.get());492 }493 494 // Drop out early, as the remaining computations are only needed for495 // reduction dependences or dependences that are finer than statement496 // level dependences.497 if (!HasReductions && Level == AL_Statement) {498 RED = isl_union_map_empty(isl_union_map_get_space(RAW));499 TC_RED = isl_union_map_empty(isl_union_set_get_space(TaggedStmtDomain));500 isl_union_set_free(TaggedStmtDomain);501 isl_union_map_free(StrictWAW);502 return;503 }504 505 isl_union_map *STMT_RAW, *STMT_WAW, *STMT_WAR;506 STMT_RAW = isl_union_map_intersect_domain(507 isl_union_map_copy(RAW), isl_union_set_copy(TaggedStmtDomain));508 STMT_WAW = isl_union_map_intersect_domain(509 isl_union_map_copy(WAW), isl_union_set_copy(TaggedStmtDomain));510 STMT_WAR =511 isl_union_map_intersect_domain(isl_union_map_copy(WAR), TaggedStmtDomain);512 POLLY_DEBUG({513 dbgs() << "Wrapped Dependences:\n";514 dump();515 dbgs() << "\n";516 });517 518 // To handle reduction dependences we proceed as follows:519 // 1) Aggregate all possible reduction dependences, namely all self520 // dependences on reduction like statements.521 // 2) Intersect them with the actual RAW & WAW dependences to the get the522 // actual reduction dependences. This will ensure the load/store memory523 // addresses were __identical__ in the two iterations of the statement.524 // 3) Relax the original RAW, WAW and WAR dependences by subtracting the525 // actual reduction dependences. Binary reductions (sum += A[i]) cause526 // the same, RAW, WAW and WAR dependences.527 // 4) Add the privatization dependences which are widened versions of528 // already present dependences. They model the effect of manual529 // privatization at the outermost possible place (namely after the last530 // write and before the first access to a reduction location).531 532 // Step 1)533 RED = isl_union_map_empty(isl_union_map_get_space(RAW));534 for (ScopStmt &Stmt : S) {535 for (MemoryAccess *MA : Stmt) {536 if (!MA->isReductionLike())537 continue;538 isl_set *AccDomW = isl_map_wrap(MA->getAccessRelation().release());539 isl_map *Identity =540 isl_map_from_domain_and_range(isl_set_copy(AccDomW), AccDomW);541 RED = isl_union_map_add_map(RED, Identity);542 }543 }544 545 // Step 2)546 RED = isl_union_map_intersect(RED, isl_union_map_copy(RAW));547 RED = isl_union_map_intersect(RED, StrictWAW);548 549 if (!isl_union_map_is_empty(RED)) {550 551 // Step 3)552 RAW = isl_union_map_subtract(RAW, isl_union_map_copy(RED));553 WAW = isl_union_map_subtract(WAW, isl_union_map_copy(RED));554 WAR = isl_union_map_subtract(WAR, isl_union_map_copy(RED));555 556 // Step 4)557 addPrivatizationDependences();558 } else559 TC_RED = isl_union_map_empty(isl_union_map_get_space(RED));560 561 POLLY_DEBUG({562 dbgs() << "Final Wrapped Dependences:\n";563 dump();564 dbgs() << "\n";565 });566 567 // RED_SIN is used to collect all reduction dependences again after we568 // split them according to the causing memory accesses. The current assumption569 // is that our method of splitting will not have any leftovers. In the end570 // we validate this assumption until we have more confidence in this method.571 isl_union_map *RED_SIN = isl_union_map_empty(isl_union_map_get_space(RAW));572 573 // For each reduction like memory access, check if there are reduction574 // dependences with the access relation of the memory access as a domain575 // (wrapped space!). If so these dependences are caused by this memory access.576 // We then move this portion of reduction dependences back to the statement ->577 // statement space and add a mapping from the memory access to these578 // dependences.579 for (ScopStmt &Stmt : S) {580 for (MemoryAccess *MA : Stmt) {581 if (!MA->isReductionLike())582 continue;583 584 isl_set *AccDomW = isl_map_wrap(MA->getAccessRelation().release());585 isl_union_map *AccRedDepU = isl_union_map_intersect_domain(586 isl_union_map_copy(TC_RED), isl_union_set_from_set(AccDomW));587 if (isl_union_map_is_empty(AccRedDepU)) {588 isl_union_map_free(AccRedDepU);589 continue;590 }591 592 isl_map *AccRedDep = isl_map_from_union_map(AccRedDepU);593 RED_SIN = isl_union_map_add_map(RED_SIN, isl_map_copy(AccRedDep));594 AccRedDep = isl_map_zip(AccRedDep);595 AccRedDep = isl_set_unwrap(isl_map_domain(AccRedDep));596 setReductionDependences(MA, AccRedDep);597 }598 }599 600 assert(isl_union_map_is_equal(RED_SIN, TC_RED) &&601 "Intersecting the reduction dependence domain with the wrapped access "602 "relation is not enough, we need to loosen the access relation also");603 isl_union_map_free(RED_SIN);604 605 RAW = isl_union_map_zip(RAW);606 WAW = isl_union_map_zip(WAW);607 WAR = isl_union_map_zip(WAR);608 RED = isl_union_map_zip(RED);609 TC_RED = isl_union_map_zip(TC_RED);610 611 POLLY_DEBUG({612 dbgs() << "Zipped Dependences:\n";613 dump();614 dbgs() << "\n";615 });616 617 RAW = isl_union_set_unwrap(isl_union_map_domain(RAW));618 WAW = isl_union_set_unwrap(isl_union_map_domain(WAW));619 WAR = isl_union_set_unwrap(isl_union_map_domain(WAR));620 RED = isl_union_set_unwrap(isl_union_map_domain(RED));621 TC_RED = isl_union_set_unwrap(isl_union_map_domain(TC_RED));622 623 POLLY_DEBUG({624 dbgs() << "Unwrapped Dependences:\n";625 dump();626 dbgs() << "\n";627 });628 629 RAW = isl_union_map_union(RAW, STMT_RAW);630 WAW = isl_union_map_union(WAW, STMT_WAW);631 WAR = isl_union_map_union(WAR, STMT_WAR);632 633 RAW = isl_union_map_coalesce(RAW);634 WAW = isl_union_map_coalesce(WAW);635 WAR = isl_union_map_coalesce(WAR);636 RED = isl_union_map_coalesce(RED);637 TC_RED = isl_union_map_coalesce(TC_RED);638 639 POLLY_DEBUG(dump());640}641 642bool Dependences::isValidSchedule(Scop &S, isl::schedule NewSched) const {643 // TODO: Also check permutable/coincident flags as well.644 645 StatementToIslMapTy NewSchedules;646 for (auto NewMap : NewSched.get_map().get_map_list()) {647 auto Stmt = reinterpret_cast<ScopStmt *>(648 NewMap.get_tuple_id(isl::dim::in).get_user());649 NewSchedules[Stmt] = NewMap;650 }651 652 return isValidSchedule(S, NewSchedules);653}654 655bool Dependences::isValidSchedule(656 Scop &S, const StatementToIslMapTy &NewSchedule) const {657 if (LegalityCheckDisabled)658 return true;659 660 isl::union_map Dependences = getDependences(TYPE_RAW | TYPE_WAW | TYPE_WAR);661 isl::union_map Schedule = isl::union_map::empty(S.getIslCtx());662 663 isl::space ScheduleSpace;664 665 for (ScopStmt &Stmt : S) {666 isl::map StmtScat;667 668 auto Lookup = NewSchedule.find(&Stmt);669 if (Lookup == NewSchedule.end())670 StmtScat = Stmt.getSchedule();671 else672 StmtScat = Lookup->second;673 assert(!StmtScat.is_null() &&674 "Schedules that contain extension nodes require special handling.");675 676 if (ScheduleSpace.is_null())677 ScheduleSpace = StmtScat.get_space().range();678 679 Schedule = Schedule.unite(StmtScat);680 }681 682 Dependences = Dependences.apply_domain(Schedule);683 Dependences = Dependences.apply_range(Schedule);684 685 isl::set Zero = isl::set::universe(ScheduleSpace);686 for (auto i : rangeIslSize(0, Zero.tuple_dim()))687 Zero = Zero.fix_si(isl::dim::set, i, 0);688 689 isl::union_set UDeltas = Dependences.deltas();690 isl::set Deltas = singleton(UDeltas, ScheduleSpace);691 692 isl::space Space = Deltas.get_space();693 isl::map NonPositive = isl::map::universe(Space.map_from_set());694 NonPositive =695 NonPositive.lex_le_at(isl::multi_pw_aff::identity_on_domain(Space));696 NonPositive = NonPositive.intersect_domain(Deltas);697 NonPositive = NonPositive.intersect_range(Zero);698 699 return NonPositive.is_empty();700}701 702// Check if the current scheduling dimension is parallel.703//704// We check for parallelism by verifying that the loop does not carry any705// dependences.706//707// Parallelism test: if the distance is zero in all outer dimensions, then it708// has to be zero in the current dimension as well.709//710// Implementation: first, translate dependences into time space, then force711// outer dimensions to be equal. If the distance is zero in the current712// dimension, then the loop is parallel. The distance is zero in the current713// dimension if it is a subset of a map with equal values for the current714// dimension.715bool Dependences::isParallel(__isl_keep isl_union_map *Schedule,716 __isl_take isl_union_map *Deps,717 __isl_give isl_pw_aff **MinDistancePtr) const {718 isl_set *Deltas, *Distance;719 isl_map *ScheduleDeps;720 unsigned Dimension;721 bool IsParallel;722 723 Deps = isl_union_map_apply_range(Deps, isl_union_map_copy(Schedule));724 Deps = isl_union_map_apply_domain(Deps, isl_union_map_copy(Schedule));725 726 if (isl_union_map_is_empty(Deps)) {727 isl_union_map_free(Deps);728 return true;729 }730 731 ScheduleDeps = isl_map_from_union_map(Deps);732 Dimension = isl_map_dim(ScheduleDeps, isl_dim_out) - 1;733 734 for (unsigned i = 0; i < Dimension; i++)735 ScheduleDeps = isl_map_equate(ScheduleDeps, isl_dim_out, i, isl_dim_in, i);736 737 Deltas = isl_map_deltas(ScheduleDeps);738 Distance = isl_set_universe(isl_set_get_space(Deltas));739 740 // [0, ..., 0, +] - All zeros and last dimension larger than zero741 for (unsigned i = 0; i < Dimension; i++)742 Distance = isl_set_fix_si(Distance, isl_dim_set, i, 0);743 744 Distance = isl_set_lower_bound_si(Distance, isl_dim_set, Dimension, 1);745 Distance = isl_set_intersect(Distance, Deltas);746 747 IsParallel = isl_set_is_empty(Distance);748 if (IsParallel || !MinDistancePtr) {749 isl_set_free(Distance);750 return IsParallel;751 }752 753 Distance = isl_set_project_out(Distance, isl_dim_set, 0, Dimension);754 Distance = isl_set_coalesce(Distance);755 756 // This last step will compute a expression for the minimal value in the757 // distance polyhedron Distance with regards to the first (outer most)758 // dimension.759 *MinDistancePtr = isl_pw_aff_coalesce(isl_set_dim_min(Distance, 0));760 761 return false;762}763 764static void printDependencyMap(raw_ostream &OS, __isl_keep isl_union_map *DM) {765 if (DM)766 OS << DM << "\n";767 else768 OS << "n/a\n";769}770 771void Dependences::print(raw_ostream &OS) const {772 OS << "\tRAW dependences:\n\t\t";773 printDependencyMap(OS, RAW);774 OS << "\tWAR dependences:\n\t\t";775 printDependencyMap(OS, WAR);776 OS << "\tWAW dependences:\n\t\t";777 printDependencyMap(OS, WAW);778 OS << "\tReduction dependences:\n\t\t";779 printDependencyMap(OS, RED);780 OS << "\tTransitive closure of reduction dependences:\n\t\t";781 printDependencyMap(OS, TC_RED);782}783 784void Dependences::dump() const { print(dbgs()); }785 786void Dependences::releaseMemory() {787 isl_union_map_free(RAW);788 isl_union_map_free(WAR);789 isl_union_map_free(WAW);790 isl_union_map_free(RED);791 isl_union_map_free(TC_RED);792 793 RED = RAW = WAR = WAW = TC_RED = nullptr;794 795 for (auto &ReductionDeps : ReductionDependences)796 isl_map_free(ReductionDeps.second);797 ReductionDependences.clear();798}799 800isl::union_map Dependences::getDependences(int Kinds) const {801 assert(hasValidDependences() && "No valid dependences available");802 isl::space Space = isl::manage_copy(RAW).get_space();803 isl::union_map Deps = Deps.empty(Space.ctx());804 805 if (Kinds & TYPE_RAW)806 Deps = Deps.unite(isl::manage_copy(RAW));807 808 if (Kinds & TYPE_WAR)809 Deps = Deps.unite(isl::manage_copy(WAR));810 811 if (Kinds & TYPE_WAW)812 Deps = Deps.unite(isl::manage_copy(WAW));813 814 if (Kinds & TYPE_RED)815 Deps = Deps.unite(isl::manage_copy(RED));816 817 if (Kinds & TYPE_TC_RED)818 Deps = Deps.unite(isl::manage_copy(TC_RED));819 820 Deps = Deps.coalesce();821 Deps = Deps.detect_equalities();822 return Deps;823}824 825bool Dependences::hasValidDependences() const {826 return (RAW != nullptr) && (WAR != nullptr) && (WAW != nullptr);827}828 829__isl_give isl_map *830Dependences::getReductionDependences(MemoryAccess *MA) const {831 return isl_map_copy(ReductionDependences.lookup(MA));832}833 834void Dependences::setReductionDependences(MemoryAccess *MA,835 __isl_take isl_map *D) {836 assert(ReductionDependences.count(MA) == 0 &&837 "Reduction dependences set twice!");838 ReductionDependences[MA] = D;839}840 841const Dependences &842DependenceAnalysis::Result::getDependences(Dependences::AnalysisLevel Level) {843 if (Dependences *d = D[Level].get())844 return *d;845 846 return recomputeDependences(Level);847}848 849const Dependences &DependenceAnalysis::Result::recomputeDependences(850 Dependences::AnalysisLevel Level) {851 D[Level].reset(new Dependences(S.getSharedIslCtx(), Level));852 D[Level]->calculateDependences(S);853 return *D[Level];854}855 856void DependenceAnalysis::Result::abandonDependences() {857 for (std::unique_ptr<Dependences> &Deps : D)858 Deps.release();859}860 861DependenceAnalysis::Result polly::runDependenceAnalysis(Scop &S) {862 DependenceAnalysis::Result Result{S, {}};863 return Result;864}865