[Polly][ForwardOpTree] Reload know values.

[Meinersbur]

Summary

For scalar accesses, change the access target to an array element that is known to contain the same value.

This may become an alternative to forwardKnownLoad which creates new loads (and therefore closer to forwarding speculatives). Reloading does not require the known value originating from a load, but can be a store as well.

The next level would be to materialize the known content's llvm::Value, if possible, without necessarily having any memory accessed at all.

polly/trunk/lib/Transform/ForwardOpTree.cpp

 
 STATISTIC(KnownAnalyzed, "Number of successfully analyzed SCoPs");
 STATISTIC(KnownOutOfQuota,
           "Analyses aborted because max_operations was reached");
 
 STATISTIC(TotalInstructionsCopied, "Number of copied instructions");
 STATISTIC(TotalKnownLoadsForwarded,
           "Number of forwarded loads because their value was known");
+STATISTIC(TotalReloads, "Number of reloaded values");
 STATISTIC(TotalReadOnlyCopied, "Number of copied read-only accesses");
 STATISTIC(TotalForwardedTrees, "Number of forwarded operand trees");
 STATISTIC(TotalModifiedStmts,
           "Number of statements with at least one forwarded tree");
 
 STATISTIC(ScopsModified, "Number of SCoPs with at least one forwarded tree");
 
 STATISTIC(NumValueWrites, "Number of scalar value writes after OpTree");
enum ForwardingDecision {
   ///
   ///   %add = add 5, 5
   ///
   /// where "5" is moved as part of a larger operand tree. "5" would be placed
   /// (disregarding for a moment that literal constants don't have a location
   /// and can be used anywhere) into the same statement as %add would.
   FD_CanForwardLeaf,
 
-  /// The root instruction can be forwarded in a non-trivial way. This requires
-  /// the operand tree root to be an instruction in some statement.
-  FD_CanForwardTree,
-
-  /// Used to indicate that a forwarding has be carried out successfully.
-  FD_DidForward,
+  /// The root instruction can be forwarded and doing so avoids a scalar
+  /// dependency.
+  ///
+  /// This can be either because the operand tree can be moved to the target
+  /// statement, or a memory access is redirected to read from a different
+  /// location.
+  FD_CanForwardProfitably,
+
+  /// Used to indicate that a forwarding has be carried out successfully, and
+  /// the forwarded memory access can be deleted.
+  FD_DidForwardTree,
+
+  /// Used to indicate that a forwarding has be carried out successfully, and
+  /// the forwarded memory access is being reused.
+  FD_DidForwardLeaf,
 
   /// A forwarding method cannot be applied to the operand tree.
   /// The difference to FD_CannotForward is that there might be other methods
   /// that can handle it.
   /// The conditions that make an operand tree applicable must be checked even
   /// with DoIt==true because a method following the one that returned
   /// FD_NotApplicable might have returned FD_CanForwardTree.
   FD_NotApplicable
private:
   IslMaxOperationsGuard &MaxOpGuard;
 
   /// How many instructions have been copied to other statements.
   int NumInstructionsCopied = 0;
 
   /// Number of loads forwarded because their value was known.
   int NumKnownLoadsForwarded = 0;
 
+  /// Number of values reloaded from known array elements.
+  int NumReloads = 0;
+
   /// How many read-only accesses have been copied.
   int NumReadOnlyCopied = 0;
 
   /// How many operand trees have been forwarded.
   int NumForwardedTrees = 0;
 
   /// Number of statements with at least one forwarded operand tree.
   int NumModifiedStmts = 0;
public:
   }
 
   void printStatistics(raw_ostream &OS, int Indent = 0) {
     OS.indent(Indent) << "Statistics {\n";
     OS.indent(Indent + 4) << "Instructions copied: " << NumInstructionsCopied
                           << '\n';
     OS.indent(Indent + 4) << "Known loads forwarded: " << NumKnownLoadsForwarded
                           << '\n';
+  OS.indent(Indent + 4) << "Reloads: " << NumReloads<< '\n';
     OS.indent(Indent + 4) << "Read-only accesses copied: " << NumReadOnlyCopied
                           << '\n';
     OS.indent(Indent + 4) << "Operand trees forwarded: " << NumForwardedTrees
                           << '\n';
     OS.indent(Indent + 4) << "Statements with forwarded operand trees: "
                           << NumModifiedStmts << '\n';
     OS.indent(Indent) << "}\n";
   }
public:
   /// @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 is not a LoadInst.
-  ///         FD_CannotForward  if no array element to load from was found.
-  ///         FD_CanForwardLeaf if the load is already in the target statement
-  ///                           instance.
-  ///         FD_CanForwardTree if @p Inst is forwardable.
-  ///         FD_DidForward     if @p DoIt was true.
+  /// @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,
                                       bool DoIt) {
     // Cannot do anything without successful known analysis.
     if (Known.is_null() || Translator.is_null() || UseToTarget.is_null() ||
         DefToTarget.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_CanForwardTree;
-
-    if (DoIt)
-      TargetStmt->prependInstruction(LI);
+      return FD_CanForwardProfitably;
 
     ForwardingDecision OpDecision =
         forwardTree(TargetStmt, LI->getPointerOperand(), DefStmt, DefLoop,
                     DefToTarget, DoIt);
     switch (OpDecision) {
     case FD_CannotForward:
       assert(!DoIt);
       return OpDecision;
 
     case FD_CanForwardLeaf:
-    case FD_CanForwardTree:
+    case FD_CanForwardProfitably:
       assert(!DoIt);
       break;
 
-    case FD_DidForward:
+    case FD_DidForwardLeaf:
+    case FD_DidForwardTree:
       assert(DoIt);
       break;
 
     default:
       llvm_unreachable("Shouldn't return this");
     }
 
     IslQuotaScope QuotaScope = MaxOpGuard.enter(!DoIt);
 
     // { DomainDef[] -> ValInst[] }
     isl::map ExpectedVal = makeValInst(Inst, UseStmt, UseLoop);
 
     // { 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);
 
     isl::map SameVal = singleLocation(Candidates, getDomainFor(TargetStmt));
     if (!SameVal)
-      return FD_CannotForward;
+      return FD_NotApplicable;
+
+    if (DoIt)
+      TargetStmt->prependInstruction(LI);
 
     if (!DoIt)
-      return FD_CanForwardTree;
+      return FD_CanForwardProfitably;
 
     if (Access) {
       DEBUG(dbgs() << "    forwarded known load with preexisting MemoryAccess"
                    << Access << "\n");
     } else {
       Access = makeReadArrayAccess(TargetStmt, LI, SameVal);
       DEBUG(dbgs() << "    forwarded known load with new MemoryAccess" << Access
                    << "\n");
ForwardingDecision forwardKnownLoad(ScopStmt *TargetStmt, Instruction *Inst,
     }
     DEBUG(dbgs() << "      expected values where " << TargetExpectedVal
                  << "\n");
     DEBUG(dbgs() << "      candidate elements where " << Candidates << "\n");
     assert(Access);
 
     NumKnownLoadsForwarded++;
     TotalKnownLoadsForwarded++;
-    return FD_DidForward;
+    return FD_DidForwardTree;
+  }
+
+  /// 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,
+                                        bool DoIt) {
+    // Cannot do anything without successful known analysis.
+    if (Known.is_null())
+      return FD_NotApplicable;
+
+    MemoryAccess *Access = TargetStmt->lookupInputAccessOf(Inst);
+    if (Access && Access->isLatestArrayKind()) {
+      if (DoIt)
+        return FD_DidForwardLeaf;
+      return FD_CanForwardLeaf;
+    }
+
+    // { DomainDef[] -> ValInst[] }
+    isl::union_map ExpectedVal = makeValInst(Inst, UseStmt, UseLoop);
+
+    // { 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);
+
+    isl::map SameVal = singleLocation(Candidates, getDomainFor(TargetStmt));
+    if (!SameVal)
+      return FD_NotApplicable;
+
+    if (!DoIt)
+      return FD_CanForwardProfitably;
+
+    if (!Access)
+      Access = TargetStmt->ensureValueRead(Inst);
+
+    simplify(SameVal);
+    Access->setNewAccessRelation(SameVal);
+
+    TotalReloads++;
+    NumReloads++;
+    return FD_DidForwardLeaf;
   }
 
   /// 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.
for (Value *OpVal : UseInst->operand_values()) {
       ForwardingDecision OpDecision =
           forwardTree(TargetStmt, OpVal, DefStmt, DefLoop, DefToTarget, DoIt);
       switch (OpDecision) {
       case FD_CannotForward:
         assert(!DoIt);
         return FD_CannotForward;
 
       case FD_CanForwardLeaf:
-      case FD_CanForwardTree:
+      case FD_CanForwardProfitably:
         assert(!DoIt);
         break;
 
-      case FD_DidForward:
+      case FD_DidForwardLeaf:
+      case FD_DidForwardTree:
         assert(DoIt);
         break;
 
       case FD_NotApplicable:
         llvm_unreachable("forwardTree should never return FD_NotApplicable");
       }
     }
 
     if (DoIt)
-      return FD_DidForward;
-    return FD_CanForwardTree;
+      return FD_DidForwardTree;
+    return FD_CanForwardProfitably;
   }
 
   /// 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.
ForwardingDecision forwardTree(ScopStmt *TargetStmt, Value *UseVal,
 
     VirtualUse VUse = VirtualUse::create(UseStmt, UseLoop, UseVal, true);
     switch (VUse.getKind()) {
     case VirtualUse::Constant:
     case VirtualUse::Block:
     case VirtualUse::Hoisted:
       // These can be used anywhere without special considerations.
       if (DoIt)
-        return FD_DidForward;
+        return FD_DidForwardTree;
       return FD_CanForwardLeaf;
 
     case VirtualUse::Synthesizable: {
       // ScopExpander will take care for of generating the code at the new
       // location.
       if (DoIt)
-        return FD_DidForward;
+        return FD_DidForwardTree;
 
       // Check if the value is synthesizable at the new location as well. This
       // might be possible when leaving a loop for which ScalarEvolution is
       // unable to derive the exit value for.
       // TODO: If there is a LCSSA PHI at the loop exit, use that one.
       // If the SCEV contains a SCEVAddRecExpr, we currently depend on that we
       // do not forward past its loop header. This would require us to use a
       // previous loop induction variable instead the current one. We currently
case VirtualUse::ReadOnly:
         return FD_CanForwardLeaf;
 
       // If we model read-only scalars, we need to create a MemoryAccess for it.
       if (ModelReadOnlyScalars)
         TargetStmt->ensureValueRead(UseVal);
 
       NumReadOnlyCopied++;
       TotalReadOnlyCopied++;
-      return FD_DidForward;
+      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:
         return SpeculativeResult;
 
       ForwardingDecision KnownResult =
           forwardKnownLoad(TargetStmt, Inst, UseStmt, UseLoop, UseToTarget,
                            DefStmt, DefLoop, DefToTarget, DoIt);
       if (KnownResult != FD_NotApplicable)
         return KnownResult;
 
+      ForwardingDecision ReloadResult =
+          reloadKnownContent(TargetStmt, Inst, UseStmt, UseLoop, UseToTarget,
+                             DefStmt, DefLoop, DefToTarget, DoIt);
+      if (ReloadResult != FD_NotApplicable)
+        return ReloadResult;
+
       // When no method is found to forward the operand tree, we effectively
       // cannot handle it.
       DEBUG(dbgs() << "    Cannot forward instruction: " << *Inst << "\n");
       return FD_CannotForward;
     }
 
     llvm_unreachable("Case unhandled");
   }
bool tryForwardTree(MemoryAccess *RA) {
     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);
-    assert(Assessment != FD_DidForward);
-    if (Assessment != FD_CanForwardTree)
+    assert(Assessment != FD_DidForwardTree && Assessment != FD_DidForwardLeaf);
+    if (Assessment != FD_CanForwardProfitably)
       return false;
 
     ForwardingDecision Execution = forwardTree(Stmt, RA->getAccessValue(), Stmt,
                                                InLoop, TargetToUse, true);
-    assert(Execution == FD_DidForward &&
+    assert(((Execution == FD_DidForwardTree) ||
+            (Execution == FD_DidForwardLeaf)) &&
            "A previous positive assessment must also be executable");
-    (void)Execution;
 
+    if (Execution == FD_DidForwardTree)
       Stmt->removeSingleMemoryAccess(RA);
     return true;
   }
 
   /// Return which SCoP this instance is processing.
   Scop *getScop() const { return S; }
 
   /// Run the algorithm: Use value read accesses as operand tree roots and try
   /// to forward them into the statement.

polly/trunk/test/ForwardOpTree/forward_store.ll

+; RUN: opt %loadPolly -polly-optree -analyze < %s | FileCheck %s -match-full-lines
+;
+; Rematerialize a load.
+;
+; for (int j = 0; j < n; j += 1) {
+; bodyA:
+;   double val = B[j];
+;
+; bodyB:
+;   A[j] = val;
+; }
+;
+
+declare double @f() #0
+
+define void @func(i32 %n, double* noalias nonnull %A, double* noalias nonnull %B) {
+entry:
+  br label %for
+
+for:
+  %j = phi i32 [0, %entry], [%j.inc, %inc]
+  %j.cmp = icmp slt i32 %j, %n
+  br i1 %j.cmp, label %bodyA, label %exit
+
+    bodyA:
+      %val = call double @f()
+      %A_idx = getelementptr inbounds double, double* %A, i32 %j
+      store double %val, double* %A_idx
+      br label %bodyB
+
+    bodyB:
+      %B_idx = getelementptr inbounds double, double* %B, i32 %j
+      store double %val, double* %B_idx
+      br label %inc
+
+inc:
+  %j.inc = add nuw nsw i32 %j, 1
+  br label %for
+
+exit:
+  br label %return
+
+return:
+  ret void
+}
+
+attributes #0 = { nounwind readnone }
+
+
+; CHECK: Statistics {
+; CHECK:     Reloads: 1
+; CHECK: }
+
+; CHECK:      After statements {
+; CHECK-NEXT:     Stmt_bodyA
+; CHECK-NEXT:             MustWriteAccess :=  [Reduction Type: NONE] [Scalar: 0]
+; CHECK-NEXT:                 [n] -> { Stmt_bodyA[i0] -> MemRef_A[i0] };
+; CHECK-NEXT:             MustWriteAccess :=  [Reduction Type: NONE] [Scalar: 1]
+; CHECK-NEXT:                 [n] -> { Stmt_bodyA[i0] -> MemRef_val[] };
+; CHECK-NEXT:             Instructions {
+; CHECK-NEXT:                   %val = call double @f()
+; CHECK-NEXT:                   store double %val, double* %A_idx
+; CHECK-NEXT:             }
+; CHECK-NEXT:     Stmt_bodyB
+; CHECK-NEXT:             MustWriteAccess :=  [Reduction Type: NONE] [Scalar: 0]
+; CHECK-NEXT:                 [n] -> { Stmt_bodyB[i0] -> MemRef_B[i0] };
+; CHECK-NEXT:             ReadAccess :=       [Reduction Type: NONE] [Scalar: 1]
+; CHECK-NEXT:                 [n] -> { Stmt_bodyB[i0] -> MemRef_val[] };
+; CHECK-NEXT:            new: [n] -> { Stmt_bodyB[i0] -> MemRef_A[i0] };
+; CHECK-NEXT:             Instructions {
+; CHECK-NEXT:                   store double %val, double* %B_idx
+; CHECK-NEXT:             }
+; CHECK-NEXT: }