Index: polly/trunk/include/polly/ZoneAlgo.h =================================================================== --- polly/trunk/include/polly/ZoneAlgo.h +++ polly/trunk/include/polly/ZoneAlgo.h @@ -154,6 +154,9 @@ /// Cache for computePerPHI(const ScopArrayInfo *) llvm::SmallDenseMap PerPHIMaps; + /// A cache for getDefToTarget(). + llvm::DenseMap, isl::map> DefToTargetCache; + /// Prepare the object before computing the zones of @p S. /// /// @param PassName Name of the pass using this analysis. @@ -192,6 +195,15 @@ void addArrayWriteAccess(MemoryAccess *MA); + /// For an llvm::Value defined in @p DefStmt, compute the RAW dependency for a + /// use in every instance of @p UseStmt. + /// + /// @param UseStmt Statement a scalar is used in. + /// @param DefStmt Statement a scalar is defined in. + /// + /// @return { DomainUse[] -> DomainDef[] } + isl::map computeUseToDefFlowDependency(ScopStmt *UseStmt, ScopStmt *DefStmt); + protected: isl::union_set makeEmptyUnionSet() const; @@ -236,6 +248,28 @@ /// The domain of the result is as narrow as possible. isl::map getAccessRelationFor(MemoryAccess *MA) const; + /// Get a domain translation map from a (scalar) definition to the statement + /// where the definition is being moved to. + /// + /// @p TargetStmt can also be seen at an llvm::Use of an llvm::Value in + /// @p DefStmt. In addition, we allow transitive uses: + /// + /// DefStmt -> MiddleStmt -> TargetStmt + /// + /// where an operand tree of instructions in DefStmt and MiddleStmt are to be + /// moved to TargetStmt. To be generally correct, we also need to know all the + /// intermediate statements. However, we make use of the fact that + /// ForwardOpTree currently does not support a move from a loop body across + /// its header such that only the first definition and the target statement + /// are relevant. + /// + /// @param DefStmt Statement from where a definition might be moved from. + /// @param TargetStmt Statement where the definition is potentially being + /// moved to (should contain a use of that definition). + /// + /// @return { DomainDef[] -> DomainTarget[] } + isl::map getDefToTarget(ScopStmt *DefStmt, ScopStmt *TargetStmt); + /// Get the reaching definition of a scalar defined in @p Stmt. /// /// Note that this does not depend on the llvm::Instruction, only on the Index: polly/trunk/lib/Transform/ForwardOpTree.cpp =================================================================== --- polly/trunk/lib/Transform/ForwardOpTree.cpp +++ polly/trunk/lib/Transform/ForwardOpTree.cpp @@ -181,9 +181,6 @@ /// original load. { ValInst[] -> ValInst[] } isl::union_map Translator; - /// A cache for getDefToTarget(). - DenseMap, isl::map> DefToTargetCache; - /// Get list of array elements that do contain the same ValInst[] at Domain[]. /// /// @param ValInst { Domain[] -> ValInst[] } @@ -374,108 +371,6 @@ return Access; } - /// For an llvm::Value defined in @p DefStmt, compute the RAW dependency for a - /// use in every instance of @p UseStmt. - /// - /// @param UseStmt Statement a scalar is used in. - /// @param DefStmt Statement a scalar is defined in. - /// - /// @return { DomainUse[] -> DomainDef[] } - isl::map computeUseToDefFlowDependency(ScopStmt *UseStmt, ScopStmt *DefStmt) { - // { DomainUse[] -> Scatter[] } - isl::map UseScatter = getScatterFor(UseStmt); - - // { Zone[] -> DomainDef[] } - isl::map ReachDefZone = getScalarReachingDefinition(DefStmt); - - // { Scatter[] -> DomainDef[] } - isl::map ReachDefTimepoints = - convertZoneToTimepoints(ReachDefZone, isl::dim::in, false, true); - - // { DomainUse[] -> DomainDef[] } - return UseScatter.apply_range(ReachDefTimepoints); - } - - /// Is @p InnerLoop nested inside @p OuterLoop? - static bool isInsideLoop(Loop *OuterLoop, Loop *InnerLoop) { - // If OuterLoop is nullptr, we cannot call its contains() method. In this - // case OuterLoop represents the 'top level' and therefore contains all - // loop. - return !OuterLoop || OuterLoop->contains(InnerLoop); - } - - /// Get a domain translation map from a (scalar) definition to the statement - /// where the definition is being moved to. - /// - /// @p TargetStmt can also be seen an llvm::Use of an llvm::Value in - /// @p DefStmt. In addition, we allow transitive uses: - /// - /// DefStmt -> MiddleStmt -> TargetStmt - /// - /// where an operand tree of instructions in DefStmt and MiddleStmt are to be - /// moved to TargetStmt. To be generally correct, we also need to know all the - /// intermediate statements. However, we make use of the fact that we - /// currently do not support a move from a loop body across its header such - /// that only the first definition and the target statement are relevant. - /// - /// @param DefStmt Statement from where a definition might be moved from. - /// @param TargetStmt Statement where the definition is potentially being - /// moved to (should contain a use of that definition). - /// - /// @return { DomainDef[] -> DomainTarget[] } - isl::map getDefToTarget(ScopStmt *DefStmt, ScopStmt *TargetStmt) { - // No translation required if the definition is already at the target. - if (TargetStmt == DefStmt) - return isl::map::identity( - getDomainFor(TargetStmt).get_space().map_from_set()); - - isl::map &Result = DefToTargetCache[std::make_pair(TargetStmt, DefStmt)]; - - // This is a shortcut in case the schedule is still the original and - // TargetStmt is in the same or nested inside DefStmt's loop. With the - // additional assumption that operand trees do not cross DefStmt's loop - // header, then TargetStmt's instance shared coordinated are the same as - // DefStmt's coordinated. All TargetStmt instances with this prefix share - // the same DefStmt instance. - // Model: - // - // for (int i < 0; i < N; i+=1) { - // DefStmt: - // D = ...; - // for (int j < 0; j < N; j+=1) { - // TargetStmt: - // use(D); - // } - // } - // - // Here, the value used in TargetStmt is defined in the corresponding - // DefStmt, i.e. - // - // { DefStmt[i] -> TargetStmt[i,j] } - // - // In practice, this should cover the majority of cases. - if (S->isOriginalSchedule() && - isInsideLoop(DefStmt->getSurroundingLoop(), - TargetStmt->getSurroundingLoop())) { - isl::set DefDomain = getDomainFor(DefStmt); - isl::set TargetDomain = getDomainFor(TargetStmt); - assert(DefDomain.dim(isl::dim::set) <= TargetDomain.dim(isl::dim::set)); - - Result = isl::map::from_domain_and_range(DefDomain, TargetDomain); - for (unsigned i = 0, DefDims = DefDomain.dim(isl::dim::set); i < DefDims; - i += 1) - Result = Result.equate(isl::dim::in, i, isl::dim::out, i); - } - - if (!Result) { - // { DomainDef[] -> DomainTarget[] } - Result = computeUseToDefFlowDependency(TargetStmt, DefStmt).reverse(); - simplify(Result); - } - - return Result; - } - /// Forward a load by reading from an array element that contains the same /// value. Typically the location it was loaded from. /// Index: polly/trunk/lib/Transform/ZoneAlgo.cpp =================================================================== --- polly/trunk/lib/Transform/ZoneAlgo.cpp +++ polly/trunk/lib/Transform/ZoneAlgo.cpp @@ -315,6 +315,13 @@ return true; } +/// Is @p InnerLoop nested inside @p OuterLoop? +static bool isInsideLoop(Loop *OuterLoop, Loop *InnerLoop) { + // If OuterLoop is nullptr, we cannot call its contains() method. In this case + // OuterLoop represents the 'top level' and therefore contains all loop. + return !OuterLoop || OuterLoop->contains(InnerLoop); +} + void ZoneAlgorithm::collectIncompatibleElts(ScopStmt *Stmt, isl::union_set &IncompatibleElts, isl::union_set &AllElts) { @@ -469,6 +476,29 @@ AllWriteValInst = AllWriteValInst.unite(EltWriteValInst); } +/// For an llvm::Value defined in @p DefStmt, compute the RAW dependency for a +/// use in every instance of @p UseStmt. +/// +/// @param UseStmt Statement a scalar is used in. +/// @param DefStmt Statement a scalar is defined in. +/// +/// @return { DomainUse[] -> DomainDef[] } +isl::map ZoneAlgorithm::computeUseToDefFlowDependency(ScopStmt *UseStmt, + ScopStmt *DefStmt) { + // { DomainUse[] -> Scatter[] } + isl::map UseScatter = getScatterFor(UseStmt); + + // { Zone[] -> DomainDef[] } + isl::map ReachDefZone = getScalarReachingDefinition(DefStmt); + + // { Scatter[] -> DomainDef[] } + isl::map ReachDefTimepoints = + convertZoneToTimepoints(ReachDefZone, isl::dim::in, false, true); + + // { DomainUse[] -> DomainDef[] } + return UseScatter.apply_range(ReachDefTimepoints); +} + /// Return whether @p PHI refers (also transitively through other PHIs) to /// itself. /// @@ -611,6 +641,60 @@ return AccRel.intersect_domain(Domain); } +isl::map ZoneAlgorithm::getDefToTarget(ScopStmt *DefStmt, + ScopStmt *TargetStmt) { + // No translation required if the definition is already at the target. + if (TargetStmt == DefStmt) + return isl::map::identity( + getDomainFor(TargetStmt).get_space().map_from_set()); + + isl::map &Result = DefToTargetCache[std::make_pair(TargetStmt, DefStmt)]; + + // This is a shortcut in case the schedule is still the original and + // TargetStmt is in the same or nested inside DefStmt's loop. With the + // additional assumption that operand trees do not cross DefStmt's loop + // header, then TargetStmt's instance shared coordinates are the same as + // DefStmt's coordinates. All TargetStmt instances with this prefix share + // the same DefStmt instance. + // Model: + // + // for (int i < 0; i < N; i+=1) { + // DefStmt: + // D = ...; + // for (int j < 0; j < N; j+=1) { + // TargetStmt: + // use(D); + // } + // } + // + // Here, the value used in TargetStmt is defined in the corresponding + // DefStmt, i.e. + // + // { DefStmt[i] -> TargetStmt[i,j] } + // + // In practice, this should cover the majority of cases. + if (!Result && S->isOriginalSchedule() && + isInsideLoop(DefStmt->getSurroundingLoop(), + TargetStmt->getSurroundingLoop())) { + isl::set DefDomain = getDomainFor(DefStmt); + isl::set TargetDomain = getDomainFor(TargetStmt); + assert(DefDomain.dim(isl::dim::set) <= TargetDomain.dim(isl::dim::set)); + + Result = isl::map::from_domain_and_range(DefDomain, TargetDomain); + for (unsigned i = 0, DefDims = DefDomain.dim(isl::dim::set); i < DefDims; + i += 1) + Result = Result.equate(isl::dim::in, i, isl::dim::out, i); + } + + if (!Result) { + // { DomainDef[] -> DomainTarget[] } + Result = computeUseToDefFlowDependency(TargetStmt, DefStmt).reverse(); + simplify(Result); + } + + return Result; +} + isl::map ZoneAlgorithm::getScalarReachingDefinition(ScopStmt *Stmt) { auto &Result = ScalarReachDefZone[Stmt]; if (Result) @@ -726,17 +810,8 @@ if (!ValStmt) return ::makeUnknownForDomain(DomainUse); - // { DomainDef[] } - auto DomainDef = getDomainFor(ValStmt); - - // { Scatter[] -> DomainDef[] } - auto ReachDef = getScalarReachingDefinition(DomainDef); - - // { DomainUse[] -> Scatter[] } - auto UserSched = getScatterFor(DomainUse); - // { DomainUse[] -> DomainDef[] } - auto UsedInstance = UserSched.apply_range(ReachDef); + auto UsedInstance = getDefToTarget(ValStmt, UserStmt).reverse(); // { llvm::Value } auto ValSet = makeValueSet(Val);