Index: polly/trunk/lib/Transform/ForwardOpTree.cpp =================================================================== --- polly/trunk/lib/Transform/ForwardOpTree.cpp +++ polly/trunk/lib/Transform/ForwardOpTree.cpp @@ -181,6 +181,9 @@ /// 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[] } @@ -393,6 +396,41 @@ return UseScatter.apply_range(ReachDefTimepoints); } + /// 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)]; + 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. /// @@ -400,14 +438,8 @@ /// @param Inst The (possibly speculatable) instruction to forward. /// @param UseStmt The statement that uses @p Inst. /// @param UseLoop The loop @p Inst is used in. - /// @param UseToTarget { DomainUse[] -> DomainTarget[] } - /// A mapping from the statement instance @p Inst is used - /// to the statement instance it is forwarded to. /// @param DefStmt The statement @p Inst is defined in. /// @param DefLoop The loop which contains @p Inst. - /// @param DefToTarget { DomainDef[] -> DomainTarget[] } - /// A mapping from the statement instance @p Inst is - /// defined to the statement instance it is forwarded to. /// @param DoIt If false, only determine whether an operand tree can be /// forwarded. If true, carry out the forwarding. Do not /// use DoIt==true if an operand tree is not known to be @@ -420,12 +452,11 @@ /// FD_DidForwardTree if @p DoIt was true. ForwardingDecision forwardKnownLoad(ScopStmt *TargetStmt, Instruction *Inst, ScopStmt *UseStmt, Loop *UseLoop, - isl::map UseToTarget, ScopStmt *DefStmt, - Loop *DefLoop, isl::map DefToTarget, + ScopStmt *DefStmt, Loop *DefLoop, bool DoIt) { // Cannot do anything without successful known analysis. - if (Known.is_null() || Translator.is_null() || UseToTarget.is_null() || - DefToTarget.is_null() || MaxOpGuard.hasQuotaExceeded()) + if (Known.is_null() || Translator.is_null() || + MaxOpGuard.hasQuotaExceeded()) return FD_NotApplicable; LoadInst *LI = dyn_cast(Inst); @@ -444,9 +475,8 @@ if (Access && !DoIt) return FD_CanForwardProfitably; - ForwardingDecision OpDecision = - forwardTree(TargetStmt, LI->getPointerOperand(), DefStmt, DefLoop, - DefToTarget, DoIt); + ForwardingDecision OpDecision = forwardTree( + TargetStmt, LI->getPointerOperand(), DefStmt, DefLoop, DoIt); switch (OpDecision) { case FD_CannotForward: assert(!DoIt); @@ -472,6 +502,9 @@ isl::map ExpectedVal = makeValInst(Inst, UseStmt, UseLoop); assert(isNormalized(ExpectedVal) && "LoadInsts are always normalized"); + // { DomainUse[] -> DomainTarget[] } + isl::map UseToTarget = getDefToTarget(UseStmt, TargetStmt); + // { DomainTarget[] -> ValInst[] } isl::map TargetExpectedVal = ExpectedVal.apply_domain(UseToTarget); isl::union_map TranslatedExpectedVal = @@ -528,6 +561,9 @@ isl::map ValToVal = isl::map::identity(ValSpace.map_from_domain_and_range(ValSpace)); + // { DomainDef[] -> DomainTarget[] } + isl::map DefToTarget = getDefToTarget(DefStmt, TargetStmt); + // { [TargetDomain[] -> Value[]] -> [DefDomain[] -> Value] } isl::map LocalTranslator = DefToTarget.reverse().product(ValToVal); @@ -554,15 +590,8 @@ /// @param Inst The scalar to forward. /// @param UseStmt The statement that uses @p Inst. /// @param UseLoop The loop @p Inst is used in. - /// @param UseToTarget { DomainUse[] -> DomainTarget[] } - /// A mapping from the statement instance @p Inst is used - /// in, to the statement instance it is forwarded to. /// @param DefStmt The statement @p Inst is defined in. /// @param DefLoop The loop which contains @p Inst. - /// @param DefToTarget { DomainDef[] -> DomainTarget[] } - /// A mapping from the statement instance @p Inst is - /// defined in, to the statement instance it is forwarded - /// to. /// @param DoIt If false, only determine whether an operand tree can be /// forwarded. If true, carry out the forwarding. Do not /// use DoIt==true if an operand tree is not known to be @@ -574,12 +603,11 @@ /// FD_DidForwardLeaf if @p DoIt was true. ForwardingDecision reloadKnownContent(ScopStmt *TargetStmt, Instruction *Inst, ScopStmt *UseStmt, Loop *UseLoop, - isl::map UseToTarget, ScopStmt *DefStmt, - Loop *DefLoop, isl::map DefToTarget, + ScopStmt *DefStmt, Loop *DefLoop, bool DoIt) { // Cannot do anything without successful known analysis. - if (Known.is_null() || Translator.is_null() || UseToTarget.is_null() || - DefToTarget.is_null() || MaxOpGuard.hasQuotaExceeded()) + if (Known.is_null() || Translator.is_null() || + MaxOpGuard.hasQuotaExceeded()) return FD_NotApplicable; MemoryAccess *Access = TargetStmt->lookupInputAccessOf(Inst); @@ -598,6 +626,9 @@ // { DomainDef[] -> ValInst[] } isl::union_map ExpectedVal = makeNormalizedValInst(Inst, UseStmt, UseLoop); + // { DomainUse[] -> DomainTarget[] } + isl::map UseToTarget = getDefToTarget(UseStmt, TargetStmt); + // { DomainTarget[] -> ValInst[] } isl::union_map TargetExpectedVal = ExpectedVal.apply_domain(UseToTarget); isl::union_map TranslatedExpectedVal = @@ -630,9 +661,6 @@ /// @param UseInst The (possibly speculatable) instruction to forward. /// @param DefStmt The statement @p UseInst is defined in. /// @param DefLoop The loop which contains @p UseInst. - /// @param DefToTarget { DomainDef[] -> DomainTarget[] } - /// A mapping from the statement instance @p UseInst is - /// defined to the statement instance it is forwarded to. /// @param DoIt If false, only determine whether an operand tree can be /// forwarded. If true, carry out the forwarding. Do not /// use DoIt==true if an operand tree is not known to be @@ -646,7 +674,7 @@ ForwardingDecision forwardSpeculatable(ScopStmt *TargetStmt, Instruction *UseInst, ScopStmt *DefStmt, Loop *DefLoop, - isl::map DefToTarget, bool DoIt) { + bool DoIt) { // PHIs, unless synthesizable, are not yet supported. if (isa(UseInst)) return FD_NotApplicable; @@ -679,7 +707,7 @@ for (Value *OpVal : UseInst->operand_values()) { ForwardingDecision OpDecision = - forwardTree(TargetStmt, OpVal, DefStmt, DefLoop, DefToTarget, DoIt); + forwardTree(TargetStmt, OpVal, DefStmt, DefLoop, DoIt); switch (OpDecision) { case FD_CannotForward: assert(!DoIt); @@ -713,9 +741,6 @@ /// operand tree. /// @param UseStmt The statement that uses @p UseVal. /// @param UseLoop The loop @p UseVal is used in. - /// @param UseToTarget { DomainUse[] -> DomainTarget[] } - /// A mapping from the statement instance @p UseVal is used - /// to the statement instance it is forwarded to. /// @param DoIt If false, only determine whether an operand tree can be /// forwarded. If true, carry out the forwarding. Do not /// use DoIt==true if an operand tree is not known to be @@ -724,8 +749,7 @@ /// @return If DoIt==false, return whether the operand tree can be forwarded. /// If DoIt==true, return FD_DidForward. ForwardingDecision forwardTree(ScopStmt *TargetStmt, Value *UseVal, - ScopStmt *UseStmt, Loop *UseLoop, - isl::map UseToTarget, bool DoIt) { + ScopStmt *UseStmt, Loop *UseLoop, bool DoIt) { ScopStmt *DefStmt = nullptr; Loop *DefLoop = nullptr; @@ -792,7 +816,6 @@ // Knowing that UseStmt and DefStmt are the same statement instance, just // reuse the information about UseStmt for DefStmt DefStmt = UseStmt; - DefToTarget = UseToTarget; LLVM_FALLTHROUGH; case VirtualUse::Inter: @@ -806,32 +829,18 @@ DefLoop = LI->getLoopFor(Inst->getParent()); - if (DefToTarget.is_null() && !Known.is_null()) { - IslQuotaScope QuotaScope = MaxOpGuard.enter(!DoIt); - - // { UseDomain[] -> DefDomain[] } - isl::map UseToDef = computeUseToDefFlowDependency(UseStmt, DefStmt); - - // { DefDomain[] -> UseDomain[] -> TargetDomain[] } shortened to - // { DefDomain[] -> TargetDomain[] } - DefToTarget = UseToTarget.apply_domain(UseToDef); - simplify(DefToTarget); - } - - ForwardingDecision SpeculativeResult = forwardSpeculatable( - TargetStmt, Inst, DefStmt, DefLoop, DefToTarget, DoIt); + ForwardingDecision SpeculativeResult = + forwardSpeculatable(TargetStmt, Inst, DefStmt, DefLoop, DoIt); if (SpeculativeResult != FD_NotApplicable) return SpeculativeResult; - ForwardingDecision KnownResult = - forwardKnownLoad(TargetStmt, Inst, UseStmt, UseLoop, UseToTarget, - DefStmt, DefLoop, DefToTarget, DoIt); + ForwardingDecision KnownResult = forwardKnownLoad( + TargetStmt, Inst, UseStmt, UseLoop, DefStmt, DefLoop, DoIt); if (KnownResult != FD_NotApplicable) return KnownResult; - ForwardingDecision ReloadResult = - reloadKnownContent(TargetStmt, Inst, UseStmt, UseLoop, UseToTarget, - DefStmt, DefLoop, DefToTarget, DoIt); + ForwardingDecision ReloadResult = reloadKnownContent( + TargetStmt, Inst, UseStmt, UseLoop, DefStmt, DefLoop, DoIt); if (ReloadResult != FD_NotApplicable) return ReloadResult; @@ -859,14 +868,14 @@ isl::map::identity(DomSpace.map_from_domain_and_range(DomSpace)); } - ForwardingDecision Assessment = forwardTree( - Stmt, RA->getAccessValue(), Stmt, InLoop, TargetToUse, false); + ForwardingDecision Assessment = + forwardTree(Stmt, RA->getAccessValue(), Stmt, InLoop, false); assert(Assessment != FD_DidForwardTree && Assessment != FD_DidForwardLeaf); if (Assessment != FD_CanForwardProfitably) return false; - ForwardingDecision Execution = forwardTree(Stmt, RA->getAccessValue(), Stmt, - InLoop, TargetToUse, true); + ForwardingDecision Execution = + forwardTree(Stmt, RA->getAccessValue(), Stmt, InLoop, true); assert(((Execution == FD_DidForwardTree) || (Execution == FD_DidForwardLeaf)) && "A previous positive assessment must also be executable");