[Polly][ForwardOpTree] Use less computationally expensive method to compute def-to-target map. NFCI.

[Meinersbur]

Summary

When forwarding a LoadInst to another statement, a map that translates their domain is needed. Before this patch, is was computed by appending the def-to-use map to the def-to-target of the operand tree's target. This patch lets the new method getDefToTarget to is. This is computationally less expensive due to:

• Caching of the result such that it can be used for multiple operands tree to the same target.
• The map is only computed when there is a LoadInst that needs it.
• It is only computed for the statement requiring the translator map, instead of having an intermediate result for every edge in the operand tree.

The downside is that this scheme cannot handle forwarding from a previous loop iteration (which would require the entire path from statement to target). Since ForwardOpTree currently does not support forwarding across loop iterations, this was not needed anyway.

This was written in reaction to the compilation timeout in GrTestUtils.cpp by the aosp-O3-polly-before-vectorizer-unprofitable buildbot. This patch may not solve the timeout itself, but would enable other mitigations such as reducing the max-computations limit for ForwardOptree or drastically simplifying the computations needed for the translator map if the schedule is still the original from ScopInfo.

[grosser]

This is a very good idea. I am out of office, but will review this Sunday night.

Tobias

[grosser]

Hi Michael,

this looks very good. I am especially interested in further optimizations for cases where the original schedule has not been changed. (What is the case currently in Polly). Just some minor nits:

"to this" -> "do this"

lib/Transform/ForwardOpTree.cpp

409 ↗

(On Diff #148646)

statements.

410 ↗

(On Diff #148646)

across

[grosser]

LGTM

polly/trunk/lib/Transform/ForwardOpTree.cpp

private:
   /// @see computeKnown()
   isl::union_map Known;
 
   /// Translator for newly introduced ValInsts to already existing ValInsts such
   /// that new introduced load instructions can reuse the Known analysis of its
   /// original load. { ValInst[] -> ValInst[] }
   isl::union_map Translator;
 
+  /// A cache for getDefToTarget().
+  DenseMap<std::pair<ScopStmt *, ScopStmt *>, isl::map> DefToTargetCache;
+
   /// Get list of array elements that do contain the same ValInst[] at Domain[].
   ///
   /// @param ValInst { Domain[] -> ValInst[] }
   ///                The values for which we search for alternative locations,
   ///                per statement instance.
   ///
   /// @return { Domain[] -> Element[] }
   ///         For each statement instance, the array elements that contain the
isl::map computeUseToDefFlowDependency(ScopStmt *UseStmt, ScopStmt *DefStmt) {
     // { Scatter[] -> DomainDef[] }
     isl::map ReachDefTimepoints =
         convertZoneToTimepoints(ReachDefZone, isl::dim::in, false, true);
 
     // { DomainUse[] -> DomainDef[] }
     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.
   ///
   /// @param TargetStmt  The statement the operand tree will be copied to.
   /// @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
   ///                    forwardable.
   ///
   /// @return FD_NotApplicable  if @p Inst cannot be forwarded by creating a new
   ///                           load.
   ///         FD_CannotForward  if the pointer operand cannot be forwarded.
   ///         FD_CanForwardProfitably if @p Inst is forwardable.
   ///         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<LoadInst>(Inst);
     if (!LI)
       return FD_NotApplicable;
 
     // If the load is already in the statement, no forwarding is necessary.
     // However, it might happen that the LoadInst is already present in the
     // statement's instruction list. In that case we do as follows:
     // - For the evaluation (DoIt==false), we can trivially forward it as it is
     //   benefit of forwarding an already present instruction.
     // - For the execution (DoIt==true), prepend the instruction (to make it
     //   available to all instructions following in the instruction list), but
     //   do not add another MemoryAccess.
     MemoryAccess *Access = TargetStmt->getArrayAccessOrNULLFor(LI);
     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);
       return OpDecision;
 
     case FD_CanForwardLeaf:
     case FD_CanForwardProfitably:
       assert(!DoIt);
ForwardingDecision forwardKnownLoad(ScopStmt *TargetStmt, Instruction *Inst,
     }
 
     IslQuotaScope QuotaScope = MaxOpGuard.enter(!DoIt);
 
     // { DomainDef[] -> ValInst[] }
     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 =
         isl::union_map(TargetExpectedVal).apply_range(Translator);
 
     // { DomainTarget[] -> Element[] }
     isl::union_map Candidates = findSameContentElements(TranslatedExpectedVal);
 
if (Access) {
 
         // { Value[] }
         isl::space ValSpace = ValInstSpace.unwrap().range();
 
         // { Value[] -> Value[] }
         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);
 
         Translator = Translator.add_map(LocalTranslator);
         LLVM_DEBUG(dbgs() << "      local translator is " << LocalTranslator
                           << "\n");
       }
     }
public:
 
   /// Forward a scalar by redirecting the access to an array element that stores
   /// the same value.
   ///
   /// @param TargetStmt  The statement the operand tree will be copied to.
   /// @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
   ///                    forwardable.
   ///
   /// @return FD_NotApplicable        if @p Inst cannot be reloaded.
   ///         FD_CanForwardLeaf       if @p Inst can be reloaded.
   ///         FD_CanForwardProfitably if @p Inst has been reloaded.
   ///         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);
     if (Access && Access->isLatestArrayKind()) {
       if (DoIt)
         return FD_DidForwardLeaf;
       return FD_CanForwardLeaf;
     }
 
     // Don't spend too much time analyzing whether it can be reloaded. When
     // carrying-out the forwarding, we cannot bail-out in the middle of the
     // transformation. It also shouldn't take as long because some results are
     // cached.
     IslQuotaScope QuotaScope = MaxOpGuard.enter(!DoIt);
 
     // { 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 =
         TargetExpectedVal.apply_range(Translator);
 
     // { DomainTarget[] -> Element[] }
     isl::union_map Candidates = findSameContentElements(TranslatedExpectedVal);
 
public:
   }
 
   /// Forwards a speculatively executable instruction.
   ///
   /// @param TargetStmt  The statement the operand tree will be copied to.
   /// @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
   ///                    forwardable.
   ///
   /// @return FD_NotApplicable  if @p UseInst is not speculatable.
   ///         FD_CannotForward  if one of @p UseInst's operands is not
   ///                           forwardable.
   ///         FD_CanForwardTree if @p UseInst is forwardable.
   ///         FD_DidForward     if @p DoIt was true.
   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<PHINode>(UseInst))
       return FD_NotApplicable;
 
     // Compatible instructions must satisfy the following conditions:
     // 1. Idempotent (instruction will be copied, not moved; although its
     //    original instance might be removed by simplification)
     // 2. Not access memory (There might be memory writes between)
if (DoIt) {
       // able to handle DAGs without duplication.
       TargetStmt->prependInstruction(UseInst);
       NumInstructionsCopied++;
       TotalInstructionsCopied++;
     }
 
     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);
         return FD_CannotForward;
 
       case FD_CanForwardLeaf:
       case FD_CanForwardProfitably:
         assert(!DoIt);
public:
   /// Determines whether an operand tree can be forwarded or carries out a
   /// forwarding, depending on the @p DoIt flag.
   ///
   /// @param TargetStmt  The statement the operand tree will be copied to.
   /// @param UseVal      The value (usually an instruction) which is root of an
   ///                    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
   ///                    forwardable.
   ///
   /// @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;
 
     // { DefDomain[] -> TargetDomain[] }
     isl::map DefToTarget;
 
     VirtualUse VUse = VirtualUse::create(UseStmt, UseLoop, UseVal, true);
     switch (VUse.getKind()) {
case VirtualUse::ReadOnly:
       NumReadOnlyCopied++;
       TotalReadOnlyCopied++;
       return FD_DidForwardLeaf;
 
     case VirtualUse::Intra:
       // 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:
       Instruction *Inst = cast<Instruction>(UseVal);
 
       if (!DefStmt) {
         DefStmt = S->getStmtFor(Inst);
         if (!DefStmt)
           return FD_CannotForward;
       }
 
       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;
 
       // When no method is found to forward the operand tree, we effectively
       // cannot handle it.
       LLVM_DEBUG(dbgs() << "    Cannot forward instruction: " << *Inst << "\n");
       return FD_CannotForward;
     }
bool tryForwardTree(MemoryAccess *RA) {
 
     isl::map TargetToUse;
     if (!Known.is_null()) {
       isl::space DomSpace = Stmt->getDomainSpace();
       TargetToUse =
           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");
 
     if (Execution == FD_DidForwardTree)
       Stmt->removeSingleMemoryAccess(RA);
     return true;
   }