1174 lines · cpp
1//===------ ZoneAlgo.cpp ----------------------------------------*- C++ -*-===//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// Derive information about array elements between statements ("Zones").10//11// The algorithms here work on the scatter space - the image space of the12// schedule returned by Scop::getSchedule(). We call an element in that space a13// "timepoint". Timepoints are lexicographically ordered such that we can14// defined ranges in the scatter space. We use two flavors of such ranges:15// Timepoint sets and zones. A timepoint set is simply a subset of the scatter16// space and is directly stored as isl_set.17//18// Zones are used to describe the space between timepoints as open sets, i.e.19// they do not contain the extrema. Using isl rational sets to express these20// would be overkill. We also cannot store them as the integer timepoints they21// contain; the (nonempty) zone between 1 and 2 would be empty and22// indistinguishable from e.g. the zone between 3 and 4. Also, we cannot store23// the integer set including the extrema; the set ]1,2[ + ]3,4[ could be24// coalesced to ]1,3[, although we defined the range [2,3] to be not in the set.25// Instead, we store the "half-open" integer extrema, including the lower bound,26// but excluding the upper bound. Examples:27//28// * The set { [i] : 1 <= i <= 3 } represents the zone ]0,3[ (which contains the29// integer points 1 and 2, but not 0 or 3)30//31// * { [1] } represents the zone ]0,1[32//33// * { [i] : i = 1 or i = 3 } represents the zone ]0,1[ + ]2,3[34//35// Therefore, an integer i in the set represents the zone ]i-1,i[, i.e. strictly36// speaking the integer points never belong to the zone. However, depending an37// the interpretation, one might want to include them. Part of the38// interpretation may not be known when the zone is constructed.39//40// Reads are assumed to always take place before writes, hence we can think of41// reads taking place at the beginning of a timepoint and writes at the end.42//43// Let's assume that the zone represents the lifetime of a variable. That is,44// the zone begins with a write that defines the value during its lifetime and45// ends with the last read of that value. In the following we consider whether a46// read/write at the beginning/ending of the lifetime zone should be within the47// zone or outside of it.48//49// * A read at the timepoint that starts the live-range loads the previous50// value. Hence, exclude the timepoint starting the zone.51//52// * A write at the timepoint that starts the live-range is not defined whether53// it occurs before or after the write that starts the lifetime. We do not54// allow this situation to occur. Hence, we include the timepoint starting the55// zone to determine whether they are conflicting.56//57// * A read at the timepoint that ends the live-range reads the same variable.58// We include the timepoint at the end of the zone to include that read into59// the live-range. Doing otherwise would mean that the two reads access60// different values, which would mean that the value they read are both alive61// at the same time but occupy the same variable.62//63// * A write at the timepoint that ends the live-range starts a new live-range.64// It must not be included in the live-range of the previous definition.65//66// All combinations of reads and writes at the endpoints are possible, but most67// of the time only the write->read (for instance, a live-range from definition68// to last use) and read->write (for instance, an unused range from last use to69// overwrite) and combinations are interesting (half-open ranges). write->write70// zones might be useful as well in some context to represent71// output-dependencies.72//73// @see convertZoneToTimepoints74//75//76// The code makes use of maps and sets in many different spaces. To not loose77// track in which space a set or map is expected to be in, variables holding an78// isl reference are usually annotated in the comments. They roughly follow isl79// syntax for spaces, but only the tuples, not the dimensions. The tuples have a80// meaning as follows:81//82// * Space[] - An unspecified tuple. Used for function parameters such that the83// function caller can use it for anything they like.84//85// * Domain[] - A statement instance as returned by ScopStmt::getDomain()86// isl_id_get_name: Stmt_<NameOfBasicBlock>87// isl_id_get_user: Pointer to ScopStmt88//89// * Element[] - An array element as in the range part of90// MemoryAccess::getAccessRelation()91// isl_id_get_name: MemRef_<NameOfArrayVariable>92// isl_id_get_user: Pointer to ScopArrayInfo93//94// * Scatter[] - Scatter space or space of timepoints95// Has no tuple id96//97// * Zone[] - Range between timepoints as described above98// Has no tuple id99//100// * ValInst[] - An llvm::Value as defined at a specific timepoint.101//102// A ValInst[] itself can be structured as one of:103//104// * [] - An unknown value.105// Always zero dimensions106// Has no tuple id107//108// * Value[] - An llvm::Value that is read-only in the SCoP, i.e. its109// runtime content does not depend on the timepoint.110// Always zero dimensions111// isl_id_get_name: Val_<NameOfValue>112// isl_id_get_user: A pointer to an llvm::Value113//114// * SCEV[...] - A synthesizable llvm::SCEV Expression.115// In contrast to a Value[] is has at least one dimension per116// SCEVAddRecExpr in the SCEV.117//118// * [Domain[] -> Value[]] - An llvm::Value that may change during the119// Scop's execution.120// The tuple itself has no id, but it wraps a map space holding a121// statement instance which defines the llvm::Value as the map's domain122// and llvm::Value itself as range.123//124// @see makeValInst()125//126// An annotation "{ Domain[] -> Scatter[] }" therefore means: A map from a127// statement instance to a timepoint, aka a schedule. There is only one scatter128// space, but most of the time multiple statements are processed in one set.129// This is why most of the time isl_union_map has to be used.130//131// The basic algorithm works as follows:132// At first we verify that the SCoP is compatible with this technique. For133// instance, two writes cannot write to the same location at the same statement134// instance because we cannot determine within the polyhedral model which one135// comes first. Once this was verified, we compute zones at which an array136// element is unused. This computation can fail if it takes too long. Then the137// main algorithm is executed. Because every store potentially trails an unused138// zone, we start at stores. We search for a scalar (MemoryKind::Value or139// MemoryKind::PHI) that we can map to the array element overwritten by the140// store, preferably one that is used by the store or at least the ScopStmt.141// When it does not conflict with the lifetime of the values in the array142// element, the map is applied and the unused zone updated as it is now used. We143// continue to try to map scalars to the array element until there are no more144// candidates to map. The algorithm is greedy in the sense that the first scalar145// not conflicting will be mapped. Other scalars processed later that could have146// fit the same unused zone will be rejected. As such the result depends on the147// processing order.148//149//===----------------------------------------------------------------------===//150 151#include "polly/ZoneAlgo.h"152#include "polly/ScopInfo.h"153#include "polly/Support/GICHelper.h"154#include "polly/Support/ISLTools.h"155#include "polly/Support/VirtualInstruction.h"156#include "llvm/ADT/Statistic.h"157#include "llvm/Support/raw_ostream.h"158 159#include "polly/Support/PollyDebug.h"160#define DEBUG_TYPE "polly-zone"161 162STATISTIC(NumIncompatibleArrays, "Number of not zone-analyzable arrays");163STATISTIC(NumCompatibleArrays, "Number of zone-analyzable arrays");164STATISTIC(NumRecursivePHIs, "Number of recursive PHIs");165STATISTIC(NumNormalizablePHIs, "Number of normalizable PHIs");166STATISTIC(NumPHINormialization, "Number of PHI executed normalizations");167 168using namespace polly;169using namespace llvm;170 171static isl::union_map computeReachingDefinition(isl::union_map Schedule,172 isl::union_map Writes,173 bool InclDef, bool InclRedef) {174 return computeReachingWrite(Schedule, Writes, false, InclDef, InclRedef);175}176 177/// Compute the reaching definition of a scalar.178///179/// Compared to computeReachingDefinition, there is just one element which is180/// accessed and therefore only a set if instances that accesses that element is181/// required.182///183/// @param Schedule { DomainWrite[] -> Scatter[] }184/// @param Writes { DomainWrite[] }185/// @param InclDef Include the timepoint of the definition to the result.186/// @param InclRedef Include the timepoint of the overwrite into the result.187///188/// @return { Scatter[] -> DomainWrite[] }189static isl::union_map computeScalarReachingDefinition(isl::union_map Schedule,190 isl::union_set Writes,191 bool InclDef,192 bool InclRedef) {193 // { DomainWrite[] -> Element[] }194 isl::union_map Defs = isl::union_map::from_domain(Writes);195 196 // { [Element[] -> Scatter[]] -> DomainWrite[] }197 auto ReachDefs =198 computeReachingDefinition(Schedule, Defs, InclDef, InclRedef);199 200 // { Scatter[] -> DomainWrite[] }201 return ReachDefs.curry().range().unwrap();202}203 204/// Compute the reaching definition of a scalar.205///206/// This overload accepts only a single writing statement as an isl_map,207/// consequently the result also is only a single isl_map.208///209/// @param Schedule { DomainWrite[] -> Scatter[] }210/// @param Writes { DomainWrite[] }211/// @param InclDef Include the timepoint of the definition to the result.212/// @param InclRedef Include the timepoint of the overwrite into the result.213///214/// @return { Scatter[] -> DomainWrite[] }215static isl::map computeScalarReachingDefinition(isl::union_map Schedule,216 isl::set Writes, bool InclDef,217 bool InclRedef) {218 isl::space DomainSpace = Writes.get_space();219 isl::space ScatterSpace = getScatterSpace(Schedule);220 221 // { Scatter[] -> DomainWrite[] }222 isl::union_map UMap = computeScalarReachingDefinition(223 Schedule, isl::union_set(Writes), InclDef, InclRedef);224 225 isl::space ResultSpace = ScatterSpace.map_from_domain_and_range(DomainSpace);226 return singleton(UMap, ResultSpace);227}228 229isl::union_map polly::makeUnknownForDomain(isl::union_set Domain) {230 return isl::union_map::from_domain(Domain);231}232 233/// Create a domain-to-unknown value mapping.234///235/// @see makeUnknownForDomain(isl::union_set)236///237/// @param Domain { Domain[] }238///239/// @return { Domain[] -> ValInst[] }240static isl::map makeUnknownForDomain(isl::set Domain) {241 return isl::map::from_domain(Domain);242}243 244/// Return whether @p Map maps to an unknown value.245///246/// @param { [] -> ValInst[] }247static bool isMapToUnknown(const isl::map &Map) {248 isl::space Space = Map.get_space().range();249 return Space.has_tuple_id(isl::dim::set).is_false() &&250 Space.is_wrapping().is_false() &&251 Space.dim(isl::dim::set).release() == 0;252}253 254isl::union_map polly::filterKnownValInst(const isl::union_map &UMap) {255 isl::union_map Result = isl::union_map::empty(UMap.ctx());256 for (isl::map Map : UMap.get_map_list()) {257 if (!isMapToUnknown(Map))258 Result = Result.unite(Map);259 }260 return Result;261}262 263ZoneAlgorithm::ZoneAlgorithm(const char *PassName, Scop *S, LoopInfo *LI)264 : PassName(PassName), IslCtx(S->getSharedIslCtx()), S(S), LI(LI),265 Schedule(S->getSchedule()) {266 auto Domains = S->getDomains();267 268 Schedule = Schedule.intersect_domain(Domains);269 ParamSpace = Schedule.get_space();270 ScatterSpace = getScatterSpace(Schedule);271}272 273/// Check if all stores in @p Stmt store the very same value.274///275/// This covers a special situation occurring in Polybench's276/// covariance/correlation (which is typical for algorithms that cover symmetric277/// matrices):278///279/// for (int i = 0; i < n; i += 1)280/// for (int j = 0; j <= i; j += 1) {281/// double x = ...;282/// C[i][j] = x;283/// C[j][i] = x;284/// }285///286/// For i == j, the same value is written twice to the same element.Double287/// writes to the same element are not allowed in DeLICM because its algorithm288/// does not see which of the writes is effective.But if its the same value289/// anyway, it doesn't matter.290///291/// LLVM passes, however, cannot simplify this because the write is necessary292/// for i != j (unless it would add a condition for one of the writes to occur293/// only if i != j).294///295/// TODO: In the future we may want to extent this to make the checks296/// specific to different memory locations.297static bool onlySameValueWrites(ScopStmt *Stmt) {298 Value *V = nullptr;299 300 for (auto *MA : *Stmt) {301 if (!MA->isLatestArrayKind() || !MA->isMustWrite() ||302 !MA->isOriginalArrayKind())303 continue;304 305 if (!V) {306 V = MA->getAccessValue();307 continue;308 }309 310 if (V != MA->getAccessValue())311 return false;312 }313 return true;314}315 316/// Is @p InnerLoop nested inside @p OuterLoop?317static bool isInsideLoop(Loop *OuterLoop, Loop *InnerLoop) {318 // If OuterLoop is nullptr, we cannot call its contains() method. In this case319 // OuterLoop represents the 'top level' and therefore contains all loop.320 return !OuterLoop || OuterLoop->contains(InnerLoop);321}322 323void ZoneAlgorithm::collectIncompatibleElts(ScopStmt *Stmt,324 isl::union_set &IncompatibleElts,325 isl::union_set &AllElts) {326 auto Stores = makeEmptyUnionMap();327 auto Loads = makeEmptyUnionMap();328 329 // This assumes that the MemoryKind::Array MemoryAccesses are iterated in330 // order.331 for (auto *MA : *Stmt) {332 if (!MA->isOriginalArrayKind())333 continue;334 335 isl::map AccRelMap = getAccessRelationFor(MA);336 isl::union_map AccRel = AccRelMap;337 338 // To avoid solving any ILP problems, always add entire arrays instead of339 // just the elements that are accessed.340 auto ArrayElts = isl::set::universe(AccRelMap.get_space().range());341 AllElts = AllElts.unite(ArrayElts);342 343 if (MA->isRead()) {344 // Reject load after store to same location.345 if (!Stores.is_disjoint(AccRel)) {346 POLLY_DEBUG(347 dbgs() << "Load after store of same element in same statement\n");348 OptimizationRemarkMissed R(PassName, "LoadAfterStore",349 MA->getAccessInstruction());350 R << "load after store of same element in same statement";351 R << " (previous stores: " << Stores;352 R << ", loading: " << AccRel << ")";353 S->getFunction().getContext().diagnose(R);354 355 IncompatibleElts = IncompatibleElts.unite(ArrayElts);356 }357 358 Loads = Loads.unite(AccRel);359 360 continue;361 }362 363 // In region statements the order is less clear, eg. the load and store364 // might be in a boxed loop.365 if (Stmt->isRegionStmt() && !Loads.is_disjoint(AccRel)) {366 POLLY_DEBUG(dbgs() << "WRITE in non-affine subregion not supported\n");367 OptimizationRemarkMissed R(PassName, "StoreInSubregion",368 MA->getAccessInstruction());369 R << "store is in a non-affine subregion";370 S->getFunction().getContext().diagnose(R);371 372 IncompatibleElts = IncompatibleElts.unite(ArrayElts);373 }374 375 // Do not allow more than one store to the same location.376 if (!Stores.is_disjoint(AccRel) && !onlySameValueWrites(Stmt)) {377 POLLY_DEBUG(dbgs() << "WRITE after WRITE to same element\n");378 OptimizationRemarkMissed R(PassName, "StoreAfterStore",379 MA->getAccessInstruction());380 R << "store after store of same element in same statement";381 R << " (previous stores: " << Stores;382 R << ", storing: " << AccRel << ")";383 S->getFunction().getContext().diagnose(R);384 385 IncompatibleElts = IncompatibleElts.unite(ArrayElts);386 }387 388 Stores = Stores.unite(AccRel);389 }390}391 392void ZoneAlgorithm::addArrayReadAccess(MemoryAccess *MA) {393 assert(MA->isLatestArrayKind());394 assert(MA->isRead());395 ScopStmt *Stmt = MA->getStatement();396 397 // { DomainRead[] -> Element[] }398 auto AccRel = intersectRange(getAccessRelationFor(MA), CompatibleElts);399 AllReads = AllReads.unite(AccRel);400 401 if (LoadInst *Load = dyn_cast_or_null<LoadInst>(MA->getAccessInstruction())) {402 // { DomainRead[] -> ValInst[] }403 isl::map LoadValInst = makeValInst(404 Load, Stmt, LI->getLoopFor(Load->getParent()), Stmt->isBlockStmt());405 406 // { DomainRead[] -> [Element[] -> DomainRead[]] }407 isl::map IncludeElement = AccRel.domain_map().curry();408 409 // { [Element[] -> DomainRead[]] -> ValInst[] }410 isl::map EltLoadValInst = LoadValInst.apply_domain(IncludeElement);411 412 AllReadValInst = AllReadValInst.unite(EltLoadValInst);413 }414}415 416isl::union_map ZoneAlgorithm::getWrittenValue(MemoryAccess *MA,417 isl::map AccRel) {418 if (!MA->isMustWrite())419 return {};420 421 Value *AccVal = MA->getAccessValue();422 ScopStmt *Stmt = MA->getStatement();423 Instruction *AccInst = MA->getAccessInstruction();424 425 // Write a value to a single element.426 auto L = MA->isOriginalArrayKind() ? LI->getLoopFor(AccInst->getParent())427 : Stmt->getSurroundingLoop();428 if (AccVal &&429 AccVal->getType() == MA->getLatestScopArrayInfo()->getElementType() &&430 AccRel.is_single_valued().is_true())431 return makeNormalizedValInst(AccVal, Stmt, L);432 433 // memset(_, '0', ) is equivalent to writing the null value to all touched434 // elements. isMustWrite() ensures that all of an element's bytes are435 // overwritten.436 if (auto *Memset = dyn_cast<MemSetInst>(AccInst)) {437 auto *WrittenConstant = dyn_cast<Constant>(Memset->getValue());438 Type *Ty = MA->getLatestScopArrayInfo()->getElementType();439 if (WrittenConstant && WrittenConstant->isZeroValue()) {440 Constant *Zero = Constant::getNullValue(Ty);441 return makeNormalizedValInst(Zero, Stmt, L);442 }443 }444 445 return {};446}447 448void ZoneAlgorithm::addArrayWriteAccess(MemoryAccess *MA) {449 assert(MA->isLatestArrayKind());450 assert(MA->isWrite());451 auto *Stmt = MA->getStatement();452 453 // { Domain[] -> Element[] }454 isl::map AccRel = intersectRange(getAccessRelationFor(MA), CompatibleElts);455 456 if (MA->isMustWrite())457 AllMustWrites = AllMustWrites.unite(AccRel);458 459 if (MA->isMayWrite())460 AllMayWrites = AllMayWrites.unite(AccRel);461 462 // { Domain[] -> ValInst[] }463 isl::union_map WriteValInstance = getWrittenValue(MA, AccRel);464 if (WriteValInstance.is_null())465 WriteValInstance = makeUnknownForDomain(Stmt);466 467 // { Domain[] -> [Element[] -> Domain[]] }468 isl::map IncludeElement = AccRel.domain_map().curry();469 470 // { [Element[] -> DomainWrite[]] -> ValInst[] }471 isl::union_map EltWriteValInst =472 WriteValInstance.apply_domain(IncludeElement);473 474 AllWriteValInst = AllWriteValInst.unite(EltWriteValInst);475}476 477/// For an llvm::Value defined in @p DefStmt, compute the RAW dependency for a478/// use in every instance of @p UseStmt.479///480/// @param UseStmt Statement a scalar is used in.481/// @param DefStmt Statement a scalar is defined in.482///483/// @return { DomainUse[] -> DomainDef[] }484isl::map ZoneAlgorithm::computeUseToDefFlowDependency(ScopStmt *UseStmt,485 ScopStmt *DefStmt) {486 // { DomainUse[] -> Scatter[] }487 isl::map UseScatter = getScatterFor(UseStmt);488 489 // { Zone[] -> DomainDef[] }490 isl::map ReachDefZone = getScalarReachingDefinition(DefStmt);491 492 // { Scatter[] -> DomainDef[] }493 isl::map ReachDefTimepoints =494 convertZoneToTimepoints(ReachDefZone, isl::dim::in, false, true);495 496 // { DomainUse[] -> DomainDef[] }497 return UseScatter.apply_range(ReachDefTimepoints);498}499 500/// Return whether @p PHI refers (also transitively through other PHIs) to501/// itself.502///503/// loop:504/// %phi1 = phi [0, %preheader], [%phi1, %loop]505/// br i1 %c, label %loop, label %exit506///507/// exit:508/// %phi2 = phi [%phi1, %bb]509///510/// In this example, %phi1 is recursive, but %phi2 is not.511static bool isRecursivePHI(const PHINode *PHI) {512 SmallVector<const PHINode *, 8> Worklist;513 SmallPtrSet<const PHINode *, 8> Visited;514 Worklist.push_back(PHI);515 516 while (!Worklist.empty()) {517 const PHINode *Cur = Worklist.pop_back_val();518 519 if (Visited.count(Cur))520 continue;521 Visited.insert(Cur);522 523 for (const Use &Incoming : Cur->incoming_values()) {524 Value *IncomingVal = Incoming.get();525 auto *IncomingPHI = dyn_cast<PHINode>(IncomingVal);526 if (!IncomingPHI)527 continue;528 529 if (IncomingPHI == PHI)530 return true;531 Worklist.push_back(IncomingPHI);532 }533 }534 return false;535}536 537isl::union_map ZoneAlgorithm::computePerPHI(const ScopArrayInfo *SAI) {538 // TODO: If the PHI has an incoming block from before the SCoP, it is not539 // represented in any ScopStmt.540 541 auto *PHI = cast<PHINode>(SAI->getBasePtr());542 auto It = PerPHIMaps.find(PHI);543 if (It != PerPHIMaps.end())544 return It->second;545 546 // Cannot reliably compute immediate predecessor for undefined executions, so547 // bail out if we do not know. This in particular applies to undefined control548 // flow.549 isl::set DefinedContext = S->getDefinedBehaviorContext();550 if (DefinedContext.is_null())551 return {};552 553 assert(SAI->isPHIKind());554 555 // { DomainPHIWrite[] -> Scatter[] }556 isl::union_map PHIWriteScatter = makeEmptyUnionMap();557 558 // Collect all incoming block timepoints.559 for (MemoryAccess *MA : S->getPHIIncomings(SAI)) {560 isl::map Scatter = getScatterFor(MA);561 PHIWriteScatter = PHIWriteScatter.unite(Scatter);562 }563 564 // { DomainPHIRead[] -> Scatter[] }565 isl::map PHIReadScatter = getScatterFor(S->getPHIRead(SAI));566 567 // { DomainPHIRead[] -> Scatter[] }568 isl::map BeforeRead = beforeScatter(PHIReadScatter, true);569 570 // { Scatter[] }571 isl::set WriteTimes = singleton(PHIWriteScatter.range(), ScatterSpace);572 573 // { DomainPHIRead[] -> Scatter[] }574 isl::map PHIWriteTimes = BeforeRead.intersect_range(WriteTimes);575 576 // Remove instances outside the context.577 PHIWriteTimes = PHIWriteTimes.intersect_params(DefinedContext);578 579 isl::map LastPerPHIWrites = PHIWriteTimes.lexmax();580 581 // { DomainPHIRead[] -> DomainPHIWrite[] }582 isl::union_map Result =583 isl::union_map(LastPerPHIWrites).apply_range(PHIWriteScatter.reverse());584 assert(!Result.is_single_valued().is_false());585 assert(!Result.is_injective().is_false());586 587 PerPHIMaps.insert({PHI, Result});588 return Result;589}590 591isl::union_set ZoneAlgorithm::makeEmptyUnionSet() const {592 return isl::union_set::empty(ParamSpace.ctx());593}594 595isl::union_map ZoneAlgorithm::makeEmptyUnionMap() const {596 return isl::union_map::empty(ParamSpace.ctx());597}598 599void ZoneAlgorithm::collectCompatibleElts() {600 // First find all the incompatible elements, then take the complement.601 // We compile the list of compatible (rather than incompatible) elements so602 // users can intersect with the list, not requiring a subtract operation. It603 // also allows us to define a 'universe' of all elements and makes it more604 // explicit in which array elements can be used.605 isl::union_set AllElts = makeEmptyUnionSet();606 isl::union_set IncompatibleElts = makeEmptyUnionSet();607 608 for (auto &Stmt : *S)609 collectIncompatibleElts(&Stmt, IncompatibleElts, AllElts);610 611 NumIncompatibleArrays += isl_union_set_n_set(IncompatibleElts.get());612 CompatibleElts = AllElts.subtract(IncompatibleElts);613 NumCompatibleArrays += isl_union_set_n_set(CompatibleElts.get());614}615 616isl::map ZoneAlgorithm::getScatterFor(ScopStmt *Stmt) const {617 isl::space ResultSpace =618 Stmt->getDomainSpace().map_from_domain_and_range(ScatterSpace);619 return Schedule.extract_map(ResultSpace);620}621 622isl::map ZoneAlgorithm::getScatterFor(MemoryAccess *MA) const {623 return getScatterFor(MA->getStatement());624}625 626isl::union_map ZoneAlgorithm::getScatterFor(isl::union_set Domain) const {627 return Schedule.intersect_domain(Domain);628}629 630isl::map ZoneAlgorithm::getScatterFor(isl::set Domain) const {631 auto ResultSpace = Domain.get_space().map_from_domain_and_range(ScatterSpace);632 auto UDomain = isl::union_set(Domain);633 auto UResult = getScatterFor(std::move(UDomain));634 auto Result = singleton(std::move(UResult), std::move(ResultSpace));635 assert(Result.is_null() || Result.domain().is_equal(Domain) == isl_bool_true);636 return Result;637}638 639isl::set ZoneAlgorithm::getDomainFor(ScopStmt *Stmt) const {640 return Stmt->getDomain().remove_redundancies();641}642 643isl::set ZoneAlgorithm::getDomainFor(MemoryAccess *MA) const {644 return getDomainFor(MA->getStatement());645}646 647isl::map ZoneAlgorithm::getAccessRelationFor(MemoryAccess *MA) const {648 auto Domain = getDomainFor(MA);649 auto AccRel = MA->getLatestAccessRelation();650 return AccRel.intersect_domain(Domain);651}652 653isl::map ZoneAlgorithm::getDefToTarget(ScopStmt *DefStmt,654 ScopStmt *TargetStmt) {655 // No translation required if the definition is already at the target.656 if (TargetStmt == DefStmt)657 return isl::map::identity(658 getDomainFor(TargetStmt).get_space().map_from_set());659 660 isl::map &Result = DefToTargetCache[std::make_pair(TargetStmt, DefStmt)];661 662 // This is a shortcut in case the schedule is still the original and663 // TargetStmt is in the same or nested inside DefStmt's loop. With the664 // additional assumption that operand trees do not cross DefStmt's loop665 // header, then TargetStmt's instance shared coordinates are the same as666 // DefStmt's coordinates. All TargetStmt instances with this prefix share667 // the same DefStmt instance.668 // Model:669 //670 // for (int i < 0; i < N; i+=1) {671 // DefStmt:672 // D = ...;673 // for (int j < 0; j < N; j+=1) {674 // TargetStmt:675 // use(D);676 // }677 // }678 //679 // Here, the value used in TargetStmt is defined in the corresponding680 // DefStmt, i.e.681 //682 // { DefStmt[i] -> TargetStmt[i,j] }683 //684 // In practice, this should cover the majority of cases.685 if (Result.is_null() && S->isOriginalSchedule() &&686 isInsideLoop(DefStmt->getSurroundingLoop(),687 TargetStmt->getSurroundingLoop())) {688 isl::set DefDomain = getDomainFor(DefStmt);689 isl::set TargetDomain = getDomainFor(TargetStmt);690 assert(unsignedFromIslSize(DefDomain.tuple_dim()) <=691 unsignedFromIslSize(TargetDomain.tuple_dim()));692 693 Result = isl::map::from_domain_and_range(DefDomain, TargetDomain);694 for (unsigned i : rangeIslSize(0, DefDomain.tuple_dim()))695 Result = Result.equate(isl::dim::in, i, isl::dim::out, i);696 }697 698 if (Result.is_null()) {699 // { DomainDef[] -> DomainTarget[] }700 Result = computeUseToDefFlowDependency(TargetStmt, DefStmt).reverse();701 simplify(Result);702 }703 704 return Result;705}706 707isl::map ZoneAlgorithm::getScalarReachingDefinition(ScopStmt *Stmt) {708 auto &Result = ScalarReachDefZone[Stmt];709 if (!Result.is_null())710 return Result;711 712 auto Domain = getDomainFor(Stmt);713 Result = computeScalarReachingDefinition(Schedule, Domain, false, true);714 simplify(Result);715 716 return Result;717}718 719isl::map ZoneAlgorithm::getScalarReachingDefinition(isl::set DomainDef) {720 auto DomId = DomainDef.get_tuple_id();721 auto *Stmt = static_cast<ScopStmt *>(isl_id_get_user(DomId.get()));722 723 auto StmtResult = getScalarReachingDefinition(Stmt);724 725 return StmtResult.intersect_range(DomainDef);726}727 728isl::map ZoneAlgorithm::makeUnknownForDomain(ScopStmt *Stmt) const {729 return ::makeUnknownForDomain(getDomainFor(Stmt));730}731 732isl::id ZoneAlgorithm::makeValueId(Value *V) {733 if (!V)734 return {};735 736 auto &Id = ValueIds[V];737 if (Id.is_null()) {738 auto Name = getIslCompatibleName("Val_", V, ValueIds.size() - 1,739 std::string(), UseInstructionNames);740 Id = isl::id::alloc(IslCtx.get(), Name.c_str(), V);741 }742 return Id;743}744 745isl::space ZoneAlgorithm::makeValueSpace(Value *V) {746 auto Result = ParamSpace.set_from_params();747 return Result.set_tuple_id(isl::dim::set, makeValueId(V));748}749 750isl::set ZoneAlgorithm::makeValueSet(Value *V) {751 auto Space = makeValueSpace(V);752 return isl::set::universe(Space);753}754 755isl::map ZoneAlgorithm::makeValInst(Value *Val, ScopStmt *UserStmt, Loop *Scope,756 bool IsCertain) {757 // If the definition/write is conditional, the value at the location could758 // be either the written value or the old value. Since we cannot know which759 // one, consider the value to be unknown.760 if (!IsCertain)761 return makeUnknownForDomain(UserStmt);762 763 auto DomainUse = getDomainFor(UserStmt);764 auto VUse = VirtualUse::create(S, UserStmt, Scope, Val, true);765 switch (VUse.getKind()) {766 case VirtualUse::Constant:767 case VirtualUse::Block:768 case VirtualUse::Hoisted:769 case VirtualUse::ReadOnly: {770 // The definition does not depend on the statement which uses it.771 auto ValSet = makeValueSet(Val);772 return isl::map::from_domain_and_range(DomainUse, ValSet);773 }774 775 case VirtualUse::Synthesizable: {776 auto *ScevExpr = VUse.getScevExpr();777 auto UseDomainSpace = DomainUse.get_space();778 779 // Construct the SCEV space.780 // TODO: Add only the induction variables referenced in SCEVAddRecExpr781 // expressions, not just all of them.782 auto ScevId = isl::manage(isl_id_alloc(UseDomainSpace.ctx().get(), nullptr,783 const_cast<SCEV *>(ScevExpr)));784 785 auto ScevSpace = UseDomainSpace.drop_dims(isl::dim::set, 0, 0);786 ScevSpace = ScevSpace.set_tuple_id(isl::dim::set, ScevId);787 788 // { DomainUse[] -> ScevExpr[] }789 auto ValInst =790 isl::map::identity(UseDomainSpace.map_from_domain_and_range(ScevSpace));791 return ValInst;792 }793 794 case VirtualUse::Intra: {795 // Definition and use is in the same statement. We do not need to compute796 // a reaching definition.797 798 // { llvm::Value }799 auto ValSet = makeValueSet(Val);800 801 // { UserDomain[] -> llvm::Value }802 auto ValInstSet = isl::map::from_domain_and_range(DomainUse, ValSet);803 804 // { UserDomain[] -> [UserDomain[] - >llvm::Value] }805 auto Result = ValInstSet.domain_map().reverse();806 simplify(Result);807 return Result;808 }809 810 case VirtualUse::Inter: {811 // The value is defined in a different statement.812 813 auto *Inst = cast<Instruction>(Val);814 auto *ValStmt = S->getStmtFor(Inst);815 816 // If the llvm::Value is defined in a removed Stmt, we cannot derive its817 // domain. We could use an arbitrary statement, but this could result in818 // different ValInst[] for the same llvm::Value.819 if (!ValStmt)820 return ::makeUnknownForDomain(DomainUse);821 822 // { DomainUse[] -> DomainDef[] }823 auto UsedInstance = getDefToTarget(ValStmt, UserStmt).reverse();824 825 // { llvm::Value }826 auto ValSet = makeValueSet(Val);827 828 // { DomainUse[] -> llvm::Value[] }829 auto ValInstSet = isl::map::from_domain_and_range(DomainUse, ValSet);830 831 // { DomainUse[] -> [DomainDef[] -> llvm::Value] }832 auto Result = UsedInstance.range_product(ValInstSet);833 834 simplify(Result);835 return Result;836 }837 }838 llvm_unreachable("Unhandled use type");839}840 841/// Remove all computed PHIs out of @p Input and replace by their incoming842/// value.843///844/// @param Input { [] -> ValInst[] }845/// @param ComputedPHIs Set of PHIs that are replaced. Its ValInst must appear846/// on the LHS of @p NormalizeMap.847/// @param NormalizeMap { ValInst[] -> ValInst[] }848static isl::union_map normalizeValInst(isl::union_map Input,849 const DenseSet<PHINode *> &ComputedPHIs,850 isl::union_map NormalizeMap) {851 isl::union_map Result = isl::union_map::empty(Input.ctx());852 for (isl::map Map : Input.get_map_list()) {853 isl::space Space = Map.get_space();854 isl::space RangeSpace = Space.range();855 856 // Instructions within the SCoP are always wrapped. Non-wrapped tuples857 // are therefore invariant in the SCoP and don't need normalization.858 if (!RangeSpace.is_wrapping()) {859 Result = Result.unite(Map);860 continue;861 }862 863 auto *PHI = dyn_cast<PHINode>(static_cast<Value *>(864 RangeSpace.unwrap().get_tuple_id(isl::dim::out).get_user()));865 866 // If no normalization is necessary, then the ValInst stands for itself.867 if (!ComputedPHIs.count(PHI)) {868 Result = Result.unite(Map);869 continue;870 }871 872 // Otherwise, apply the normalization.873 isl::union_map Mapped = isl::union_map(Map).apply_range(NormalizeMap);874 Result = Result.unite(Mapped);875 NumPHINormialization++;876 }877 return Result;878}879 880isl::union_map ZoneAlgorithm::makeNormalizedValInst(llvm::Value *Val,881 ScopStmt *UserStmt,882 llvm::Loop *Scope,883 bool IsCertain) {884 isl::map ValInst = makeValInst(Val, UserStmt, Scope, IsCertain);885 isl::union_map Normalized =886 normalizeValInst(ValInst, ComputedPHIs, NormalizeMap);887 return Normalized;888}889 890bool ZoneAlgorithm::isCompatibleAccess(MemoryAccess *MA) {891 if (!MA)892 return false;893 if (!MA->isLatestArrayKind())894 return false;895 Instruction *AccInst = MA->getAccessInstruction();896 return isa<StoreInst>(AccInst) || isa<LoadInst>(AccInst);897}898 899bool ZoneAlgorithm::isNormalizable(MemoryAccess *MA) {900 assert(MA->isRead());901 902 // Exclude ExitPHIs, we are assuming that a normalizable PHI has a READ903 // MemoryAccess.904 if (!MA->isOriginalPHIKind())905 return false;906 907 // Exclude recursive PHIs, normalizing them would require a transitive908 // closure.909 auto *PHI = cast<PHINode>(MA->getAccessInstruction());910 if (RecursivePHIs.count(PHI))911 return false;912 913 // Ensure that each incoming value can be represented by a ValInst[].914 // We do represent values from statements associated to multiple incoming915 // value by the PHI itself, but we do not handle this case yet (especially916 // isNormalized()) when normalizing.917 const ScopArrayInfo *SAI = MA->getOriginalScopArrayInfo();918 auto Incomings = S->getPHIIncomings(SAI);919 for (MemoryAccess *Incoming : Incomings) {920 if (Incoming->getIncoming().size() != 1)921 return false;922 }923 924 return true;925}926 927isl::boolean ZoneAlgorithm::isNormalized(isl::map Map) {928 isl::space Space = Map.get_space();929 isl::space RangeSpace = Space.range();930 931 isl::boolean IsWrapping = RangeSpace.is_wrapping();932 if (!IsWrapping.is_true())933 return !IsWrapping;934 isl::space Unwrapped = RangeSpace.unwrap();935 936 isl::id OutTupleId = Unwrapped.get_tuple_id(isl::dim::out);937 if (OutTupleId.is_null())938 return isl::boolean();939 auto *PHI = dyn_cast<PHINode>(static_cast<Value *>(OutTupleId.get_user()));940 if (!PHI)941 return true;942 943 isl::id InTupleId = Unwrapped.get_tuple_id(isl::dim::in);944 if (OutTupleId.is_null())945 return isl::boolean();946 auto *IncomingStmt = static_cast<ScopStmt *>(InTupleId.get_user());947 MemoryAccess *PHIRead = IncomingStmt->lookupPHIReadOf(PHI);948 if (!isNormalizable(PHIRead))949 return true;950 951 return false;952}953 954isl::boolean ZoneAlgorithm::isNormalized(isl::union_map UMap) {955 isl::boolean Result = true;956 for (isl::map Map : UMap.get_map_list()) {957 Result = isNormalized(Map);958 if (Result.is_true())959 continue;960 break;961 }962 return Result;963}964 965void ZoneAlgorithm::computeCommon() {966 AllReads = makeEmptyUnionMap();967 AllMayWrites = makeEmptyUnionMap();968 AllMustWrites = makeEmptyUnionMap();969 AllWriteValInst = makeEmptyUnionMap();970 AllReadValInst = makeEmptyUnionMap();971 972 // Default to empty, i.e. no normalization/replacement is taking place. Call973 // computeNormalizedPHIs() to initialize.974 NormalizeMap = makeEmptyUnionMap();975 ComputedPHIs.clear();976 977 for (auto &Stmt : *S) {978 for (auto *MA : Stmt) {979 if (!MA->isLatestArrayKind())980 continue;981 982 if (MA->isRead())983 addArrayReadAccess(MA);984 985 if (MA->isWrite())986 addArrayWriteAccess(MA);987 }988 }989 990 // { DomainWrite[] -> Element[] }991 AllWrites = AllMustWrites.unite(AllMayWrites);992 993 // { [Element[] -> Zone[]] -> DomainWrite[] }994 WriteReachDefZone =995 computeReachingDefinition(Schedule, AllWrites, false, true);996 simplify(WriteReachDefZone);997}998 999void ZoneAlgorithm::computeNormalizedPHIs() {1000 // Determine which PHIs can reference themselves. They are excluded from1001 // normalization to avoid problems with transitive closures.1002 for (ScopStmt &Stmt : *S) {1003 for (MemoryAccess *MA : Stmt) {1004 if (!MA->isPHIKind())1005 continue;1006 if (!MA->isRead())1007 continue;1008 1009 // TODO: Can be more efficient since isRecursivePHI can theoretically1010 // determine recursiveness for multiple values and/or cache results.1011 auto *PHI = cast<PHINode>(MA->getAccessInstruction());1012 if (isRecursivePHI(PHI)) {1013 NumRecursivePHIs++;1014 RecursivePHIs.insert(PHI);1015 }1016 }1017 }1018 1019 // { PHIValInst[] -> IncomingValInst[] }1020 isl::union_map AllPHIMaps = makeEmptyUnionMap();1021 1022 // Discover new PHIs and try to normalize them.1023 DenseSet<PHINode *> AllPHIs;1024 for (ScopStmt &Stmt : *S) {1025 for (MemoryAccess *MA : Stmt) {1026 if (!MA->isOriginalPHIKind())1027 continue;1028 if (!MA->isRead())1029 continue;1030 if (!isNormalizable(MA))1031 continue;1032 1033 auto *PHI = cast<PHINode>(MA->getAccessInstruction());1034 const ScopArrayInfo *SAI = MA->getOriginalScopArrayInfo();1035 1036 // Determine which instance of the PHI statement corresponds to which1037 // incoming value. Skip if we cannot determine PHI predecessors.1038 // { PHIDomain[] -> IncomingDomain[] }1039 isl::union_map PerPHI = computePerPHI(SAI);1040 if (PerPHI.is_null())1041 continue;1042 1043 // { PHIDomain[] -> PHIValInst[] }1044 isl::map PHIValInst = makeValInst(PHI, &Stmt, Stmt.getSurroundingLoop());1045 1046 // { IncomingDomain[] -> IncomingValInst[] }1047 isl::union_map IncomingValInsts = makeEmptyUnionMap();1048 1049 // Get all incoming values.1050 for (MemoryAccess *MA : S->getPHIIncomings(SAI)) {1051 ScopStmt *IncomingStmt = MA->getStatement();1052 1053 auto Incoming = MA->getIncoming();1054 assert(Incoming.size() == 1 && "The incoming value must be "1055 "representable by something else than "1056 "the PHI itself");1057 Value *IncomingVal = Incoming[0].second;1058 1059 // { IncomingDomain[] -> IncomingValInst[] }1060 isl::map IncomingValInst = makeValInst(1061 IncomingVal, IncomingStmt, IncomingStmt->getSurroundingLoop());1062 1063 IncomingValInsts = IncomingValInsts.unite(IncomingValInst);1064 }1065 1066 // { PHIValInst[] -> IncomingValInst[] }1067 isl::union_map PHIMap =1068 PerPHI.apply_domain(PHIValInst).apply_range(IncomingValInsts);1069 assert(!PHIMap.is_single_valued().is_false());1070 1071 // Resolve transitiveness: The incoming value of the newly discovered PHI1072 // may reference a previously normalized PHI. At the same time, already1073 // normalized PHIs might be normalized to the new PHI. At the end, none of1074 // the PHIs may appear on the right-hand-side of the normalization map.1075 PHIMap = normalizeValInst(PHIMap, AllPHIs, AllPHIMaps);1076 AllPHIs.insert(PHI);1077 AllPHIMaps = normalizeValInst(AllPHIMaps, AllPHIs, PHIMap);1078 1079 AllPHIMaps = AllPHIMaps.unite(PHIMap);1080 NumNormalizablePHIs++;1081 }1082 }1083 simplify(AllPHIMaps);1084 1085 // Apply the normalization.1086 ComputedPHIs = AllPHIs;1087 NormalizeMap = AllPHIMaps;1088 1089 assert(NormalizeMap.is_null() || isNormalized(NormalizeMap));1090}1091 1092void ZoneAlgorithm::printAccesses(llvm::raw_ostream &OS, int Indent) const {1093 OS.indent(Indent) << "After accesses {\n";1094 for (auto &Stmt : *S) {1095 OS.indent(Indent + 4) << Stmt.getBaseName() << "\n";1096 for (auto *MA : Stmt)1097 MA->print(OS);1098 }1099 OS.indent(Indent) << "}\n";1100}1101 1102isl::union_map ZoneAlgorithm::computeKnownFromMustWrites() const {1103 // { [Element[] -> Zone[]] -> [Element[] -> DomainWrite[]] }1104 isl::union_map EltReachdDef = distributeDomain(WriteReachDefZone.curry());1105 1106 // { [Element[] -> DomainWrite[]] -> ValInst[] }1107 isl::union_map AllKnownWriteValInst = filterKnownValInst(AllWriteValInst);1108 1109 // { [Element[] -> Zone[]] -> ValInst[] }1110 return EltReachdDef.apply_range(AllKnownWriteValInst);1111}1112 1113isl::union_map ZoneAlgorithm::computeKnownFromLoad() const {1114 // { Element[] }1115 isl::union_set AllAccessedElts = AllReads.range().unite(AllWrites.range());1116 1117 // { Element[] -> Scatter[] }1118 isl::union_map EltZoneUniverse = isl::union_map::from_domain_and_range(1119 AllAccessedElts, isl::set::universe(ScatterSpace));1120 1121 // This assumes there are no "holes" in1122 // isl_union_map_domain(WriteReachDefZone); alternatively, compute the zone1123 // before the first write or that are not written at all.1124 // { Element[] -> Scatter[] }1125 isl::union_set NonReachDef =1126 EltZoneUniverse.wrap().subtract(WriteReachDefZone.domain());1127 1128 // { [Element[] -> Zone[]] -> ReachDefId[] }1129 isl::union_map DefZone =1130 WriteReachDefZone.unite(isl::union_map::from_domain(NonReachDef));1131 1132 // { [Element[] -> Scatter[]] -> Element[] }1133 isl::union_map EltZoneElt = EltZoneUniverse.domain_map();1134 1135 // { [Element[] -> Zone[]] -> [Element[] -> ReachDefId[]] }1136 isl::union_map DefZoneEltDefId = EltZoneElt.range_product(DefZone);1137 1138 // { Element[] -> [Zone[] -> ReachDefId[]] }1139 isl::union_map EltDefZone = DefZone.curry();1140 1141 // { [Element[] -> Zone[] -> [Element[] -> ReachDefId[]] }1142 isl::union_map EltZoneEltDefid = distributeDomain(EltDefZone);1143 1144 // { [Element[] -> Scatter[]] -> DomainRead[] }1145 isl::union_map Reads = AllReads.range_product(Schedule).reverse();1146 1147 // { [Element[] -> Scatter[]] -> [Element[] -> DomainRead[]] }1148 isl::union_map ReadsElt = EltZoneElt.range_product(Reads);1149 1150 // { [Element[] -> Scatter[]] -> ValInst[] }1151 isl::union_map ScatterKnown = ReadsElt.apply_range(AllReadValInst);1152 1153 // { [Element[] -> ReachDefId[]] -> ValInst[] }1154 isl::union_map DefidKnown =1155 DefZoneEltDefId.apply_domain(ScatterKnown).reverse();1156 1157 // { [Element[] -> Zone[]] -> ValInst[] }1158 return DefZoneEltDefId.apply_range(DefidKnown);1159}1160 1161isl::union_map ZoneAlgorithm::computeKnown(bool FromWrite,1162 bool FromRead) const {1163 isl::union_map Result = makeEmptyUnionMap();1164 1165 if (FromWrite)1166 Result = Result.unite(computeKnownFromMustWrites());1167 1168 if (FromRead)1169 Result = Result.unite(computeKnownFromLoad());1170 1171 simplify(Result);1172 return Result;1173}1174