[ForwardOp] Remove read accesses for all instructions that have been moved

[grosser]

Summary

Before this change only the memory accesses belonging to the roots of the
operand trees were removed, this resulted in some redundant reads, but more
importantly also caused crashes in the code generation, as instructions for
which a read access still existed where modeled as inter-statement use, which
caused polly-simplify's mark-and-sweep algorithm to not reach these statements,
which resulted in dropped instructions and consequently broken code.

[Meinersbur]

Forwarded instructions may have uses remaining in the same statement, removing the MemoryAccess will leave it without a value to use and crash in codegen. This is why removing access has to be deferred to -polly-simplify.

The test-case forward_load_tripleuse doesn't crash in codegen, even with a -polly-simplify inserted. However, the result for func2 looks strange. I'll take a look.

[grosser]

Add failing test case

[grosser]

Hi Michael,

I forgot to add the failing test case. It breaks with -polly-optree -polly-simplify -polly-codegen.

Best,
Tobias

[Meinersbur]

Hi Tobias.

thank for uploading the test case.

This fixes the problem:

diff --git a/lib/Transform/ForwardOpTree.cpp b/lib/Transform/ForwardOpTree.cpp
index dffd3cb1..78ff481f 100644
--- a/lib/Transform/ForwardOpTree.cpp
+++ b/lib/Transform/ForwardOpTree.cpp
@@ -419,7 +419,7 @@ public:
     //   available to all instructions following in the instruction list), but
     //   do not add another MemoryAccess.
     MemoryAccess *Access = TargetStmt->getArrayAccessOrNULLFor(LI);
-    if (Access && !DoIt)
+    if (Access && TargetStmt != UseStmt && !DoIt)
       return FD_CanForwardLeaf;

     if (DoIt)

We could improve the robustness of VirtualUse by giving priority to whether the value is in the instruction list (over looking for input MemoryAccesses). It would allow ignoring the input MemoryAccess when the value is available as intra- and inter-access. The explicit instruction list did not exist when VirtualUse was designed.

[Meinersbur]

The entire return FD_ForwardTree might be useless for forwarding loads, we always want to forward a load if it is accessed through its scalar (which is always the case, forwardOperandTrees only ever tries to forward scalars). This might be the better patch:

diff --git a/lib/Transform/ForwardOpTree.cpp b/lib/Transform/ForwardOpTree.cpp
index 894f8097..8f44cf33 100644
--- a/lib/Transform/ForwardOpTree.cpp
+++ b/lib/Transform/ForwardOpTree.cpp
@@ -420,7 +420,7 @@ public:
     //   do not add another MemoryAccess.
     MemoryAccess *Access = TargetStmt->getArrayAccessOrNULLFor(LI);
     if (Access && !DoIt)
-      return FD_CanForwardLeaf;
+      return FD_CanForwardTree;

     if (DoIt)
       TargetStmt->prependInstruction(LI);

[grosser]

Use Michael's suggested change

[grosser]

This seems to work, but my commit message is not very good yet. Can you suggest a commit message that describes the reason you prefer this solution?

[Meinersbur]

I assume that not everyone subscribed to llvm-commits knows that "ForwardOpTree"/"ForwardOp" is a component of Polly. The tag "[Polly]" might still be useful.

In D37424#859999, @grosser wrote:

This seems to work, but my commit message is not very good yet. Can you suggest a commit message that describes the reason you prefer this solution?

Before this patch, OpTree did not consider forwarding an operand tree consisting of only single LoadInst as useful. The motivation was that, like an access to a read-only variable, it would just replace one MemoryAccess by another. However, in contrast to read-only accesses, this would replace a scalar access by an array access, which is something worth doing.

In addition, leaving scalar MemoryAccess is problematic in that VirtualUse prioritizes inter-Stmt use over intra-Stmt. It was possible that the same LLVM value has a MemoryAccess for accessing the remote Stmt's LoadInst as well as having the same LoadInst in its own instruction list (due to being forwarded from another operand tree).

With this patch we ensure that if a LoadInst is forwarded is any operand tree, also the operand tree containing just the LoadInst is forwarded as well, which effectively removes the scalar MemoryAccess such that only the array access remains, not both.

lib/Transform/ForwardOpTree.cpp

public:
   /// @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 MovedInsts  A set in which the newly added instructions will be
+  ///                    recorded.
   /// @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.
-  ForwardingDecision forwardKnownLoad(ScopStmt *TargetStmt, Instruction *Inst,
-                                      ScopStmt *UseStmt, Loop *UseLoop,
-                                      isl::map UseToTarget, ScopStmt *DefStmt,
-                                      Loop *DefLoop, isl::map DefToTarget,
-                                      bool DoIt) {
+  ForwardingDecision
+  forwardKnownLoad(ScopStmt *TargetStmt, Instruction *Inst, ScopStmt *UseStmt,
+                   Loop *UseLoop, isl::map UseToTarget, ScopStmt *DefStmt,
+                   SmallVectorImpl<Instruction *> &MovedInsts, bool DoIt) {
     // Cannot do anything without successful known analysis.
     if (Known.is_null())
       return FD_NotApplicable;
 
     LoadInst *LI = dyn_cast<LoadInst>(Inst);
     if (!LI)
       return FD_NotApplicable;
 
     // If the load is already in the statement, not 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==false), 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_CanForwardLeaf;
 
-    if (DoIt)
+    if (DoIt) {
       TargetStmt->prependInstruction(LI);
+      MovedInsts.push_back(LI);
+    }
 
     ForwardingDecision OpDecision =
         forwardTree(TargetStmt, LI->getPointerOperand(), DefStmt, DefLoop,
-                    DefToTarget, DoIt);
+                    DefToTarget, MovedInsts, DoIt);
     switch (OpDecision) {
     case FD_CannotForward:
       assert(!DoIt);
       return OpDecision;
 
     case FD_CanForwardLeaf:
     case FD_CanForwardTree:
       assert(!DoIt);
public:
   ///
   /// @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 MovedInsts  A set in which the newly added instructions will be
+  ///                    recorded.
   /// @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) {
+  ForwardingDecision
+  forwardSpeculatable(ScopStmt *TargetStmt, Instruction *UseInst,
+                      ScopStmt *DefStmt, Loop *DefLoop, isl::map DefToTarget,
+                      SmallVectorImpl<Instruction *> &MovedInsts, 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)
forwardSpeculatable(ScopStmt *TargetStmt, Instruction *UseInst,
 
     if (DoIt) {
       // To ensure the right order, prepend this instruction before its
       // operands. This ensures that its operands are inserted before the
       // instruction using them.
       // TODO: The operand tree is not really a tree, but a DAG. We should be
       // able to handle DAGs without duplication.
       TargetStmt->prependInstruction(UseInst);
+      MovedInsts.push_back(UseInst);
       NumInstructionsCopied++;
       TotalInstructionsCopied++;
     }
 
     for (Value *OpVal : UseInst->operand_values()) {
-      ForwardingDecision OpDecision =
-          forwardTree(TargetStmt, OpVal, DefStmt, DefLoop, DefToTarget, DoIt);
+      ForwardingDecision OpDecision = forwardTree(
+          TargetStmt, OpVal, DefStmt, DefLoop, DefToTarget, MovedInsts, DoIt);
       switch (OpDecision) {
       case FD_CannotForward:
         assert(!DoIt);
         return FD_CannotForward;
 
       case FD_CanForwardLeaf:
       case FD_CanForwardTree:
         assert(!DoIt);
public:
   /// @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 MovedInsts  A set in which the newly added instructions will be
+  ///                    recorded.
   /// @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) {
+                                 isl::map UseToTarget,
+                                 SmallVectorImpl<Instruction *> &MovedInsts,
+                                 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::Inter:
 
         // { DefDomain[] -> UseDomain[] -> TargetDomain[] } shortened to
         // { DefDomain[] -> TargetDomain[] }
         DefToTarget = UseToTarget.apply_domain(UseToDef);
         simplify(DefToTarget);
       }
 
       ForwardingDecision SpeculativeResult = forwardSpeculatable(
-          TargetStmt, Inst, DefStmt, DefLoop, DefToTarget, DoIt);
+          TargetStmt, Inst, DefStmt, DefLoop, DefToTarget, MovedInsts, DoIt);
       if (SpeculativeResult != FD_NotApplicable)
         return SpeculativeResult;
 
       ForwardingDecision KnownResult =
           forwardKnownLoad(TargetStmt, Inst, UseStmt, UseLoop, UseToTarget,
-                           DefStmt, DefLoop, DefToTarget, DoIt);
+                           DefStmt, DefLoop, DefToTarget, MovedInsts, DoIt);
       if (KnownResult != FD_NotApplicable)
         return KnownResult;
 
       // 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");
   }
 
   /// Try to forward an operand tree rooted in @p RA.
-  bool tryForwardTree(MemoryAccess *RA) {
+  bool tryForwardTree(MemoryAccess *RA,
+                      SmallVectorImpl<Instruction *> &MovedInsts) {
     assert(RA->isLatestScalarKind());
     DEBUG(dbgs() << "Trying to forward operand tree " << RA << "...\n");
 
     ScopStmt *Stmt = RA->getStatement();
     Loop *InLoop = Stmt->getSurroundingLoop();
 
     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, TargetToUse,
+                    MovedInsts, false);
     assert(Assessment != FD_DidForward);
     if (Assessment != FD_CanForwardTree)
       return false;
 
-    ForwardingDecision Execution = forwardTree(Stmt, RA->getAccessValue(), Stmt,
-                                               InLoop, TargetToUse, true);
+    ForwardingDecision Execution =
+        forwardTree(Stmt, RA->getAccessValue(), Stmt, InLoop, TargetToUse,
+                    MovedInsts, true);
     assert(Execution == FD_DidForward &&
            "A previous positive assessment must also be executable");
     (void)Execution;
-
-    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.
   bool forwardOperandTrees() {
     for (ScopStmt &Stmt : *S) {
       bool StmtModified = false;
 
       // Because we are modifying the MemoryAccess list, collect them first to
       // avoid iterator invalidation.
       SmallVector<MemoryAccess *, 16> Accs;
       for (MemoryAccess *RA : Stmt) {
         if (!RA->isRead())
           continue;
         if (!RA->isLatestScalarKind())
           continue;
 
         Accs.push_back(RA);
       }
 
+      SmallVector<Instruction *, 16> MovedInsts;
+
       for (MemoryAccess *RA : Accs) {
-        if (tryForwardTree(RA)) {
+        if (tryForwardTree(RA, MovedInsts)) {
           Modified = true;
           StmtModified = true;
           NumForwardedTrees++;
           TotalForwardedTrees++;
         }
       }
 
+      for (Instruction *Inst : MovedInsts) {
+        MemoryAccess *MA = Stmt.lookupInputAccessOf(Inst);
+        if (MA)
+          Stmt.removeSingleMemoryAccess(MA);
+      }
+
       if (StmtModified) {
         NumModifiedStmts++;
         TotalModifiedStmts++;
       }
     }
 
     if (Modified)
       ScopsModified++;

test/ForwardOpTree/forward_load_tripleuse.ll

 ; CHECK-NEXT:     Stmt_bodyB
 ; CHECK-NEXT:             ReadAccess :=       [Reduction Type: NONE] [Scalar: 0]
 ; CHECK-NEXT:                 null;
 ; CHECK-NEXT:            new: [n] -> { Stmt_bodyB[i0] -> MemRef_A[i0] };
 ; CHECK-NEXT:             MustWriteAccess :=  [Reduction Type: NONE] [Scalar: 0]
 ; CHECK-NEXT:                 [n] -> { Stmt_bodyB[i0] -> MemRef_B[i0] };
 ; CHECK-NEXT:             MustWriteAccess :=  [Reduction Type: NONE] [Scalar: 0]
 ; CHECK-NEXT:                 [n] -> { Stmt_bodyB[i0] -> MemRef_C[i0] };
-; CHECK-NEXT:             ReadAccess :=       [Reduction Type: NONE] [Scalar: 1]
-; CHECK-NEXT:                 [n] -> { Stmt_bodyB[i0] -> MemRef_val1[] };
 ; CHECK-NEXT:             Instructions {
 ; CHECK-NEXT:                   %val1 = load double, double* %A_idx
 ; CHECK-NEXT:                   %val1 = load double, double* %A_idx
 ; CHECK-NEXT:                   %val2 = fadd double %val1, %val1
 ; CHECK-NEXT:                   store double %val2, double* %B_idx
 ; CHECK-NEXT:                   store double %val1, double* %C_idx
 ; CHECK-NEXT:             }
 ; CHECK-NEXT: }