[ForwardOpTree] Allow forwarding in the presence of region statements

[grosser]

Summary

After region statements now also have instruction lists, this is a
straightforward extension.

[Meinersbur]

lib/Analysis/ScopInfo.cpp

1740–1756 ↗

(On Diff #113268)

[Suggestion] Wouldn't is be easier to enumerate over Scop::getBoxedLoops() and check those whether they are contained in the stmt?

1749–1753 ↗

(On Diff #113268)

I assume this is for the case L==nullptr. Could be put into the else branch. of if (L)

lib/Transform/ZoneAlgo.cpp

379 ↗

(On Diff #113268)

[Serious] Boxed loops are not the only problematic case. Consider within a region stmt:

  br label %StmtB

StmtA:
  %a= load %A
  br label %StmtC  

StmtB:
  store %A 
  br label %StmtA  

StmtC:
  ...

Iteration order might be StmtA first, then StmtB, although StmtB is executed before StmtA. It should be rejected, but is not.

381–384 ↗

(On Diff #113268)

Message should be changed to the new meaning.

test/DeLICM/reject_storeinsubregion.ll

78–85 ↗

(On Diff #113268)

This was a check the case when it does _not_ work. Please ensure that we still have a test case for the not-allowed case.

test/ForwardOpTree/forward_region.ll

10 ↗

(On Diff #113268)

This condition does not correspond to the IR below.

test/ForwardOpTree/noforward_region.ll

1 ↗

(On Diff #113268)

Why is this deleted? There are still cases in regions that are not allowed.

[grosser]

Thank you. Looking into it.

lib/Analysis/ScopInfo.cpp

1740–1756 ↗

(On Diff #113268)

This would grow linearly in the size of the scop, whereas the current approach hopefully would not.

lib/Transform/ZoneAlgo.cpp

379 ↗

(On Diff #113268)

OK. What would you suggest to check instead?

381–384 ↗

(On Diff #113268)

OK.

test/ForwardOpTree/forward_region.ll

10 ↗

(On Diff #113268)

I just moved the old test case. Will cross-check.

test/ForwardOpTree/noforward_region.ll

1 ↗

(On Diff #113268)

OK.

[Meinersbur]

lib/Analysis/ScopInfo.cpp

1740–1756 ↗

(On Diff #113268)

You can check whether a given BB is in a boxed loop in constant time (assuming hashtable lookup is constant time):

LI.getLoopFor(BB) != Stmt.getSurroundingLoop()

I think closer to what is actually needed, no?

lib/Transform/ZoneAlgo.cpp

379 ↗

(On Diff #113268)

If you want to keep it easy, leave it as it is. It would only have an effect for load-forwarding from region stmts (not to region stmt, which seems to be the case you are interested in) (and DeLICM to some extent).
In contrast to my previous assumption this is possible without crossing a phi node: if the load to be forwarded is in the region's entry block (or in strange cases of irreducible loops)

If you want to make it work, you can check the following:

• Allow reads and writes in the entry block (if not part of a boxed loop which can be checked in constant time as show above; to also cover the case of an irreducible loop which is I am not sure is possible: check that all incoming edges are from outside the region; the point is only to ensure that the BB is not executed multiple times in the same statement instance) like it is done for block stmts (which never have boxed loops).
• Disallow any writes in non-entry blocks, as it is now for all BBs in region stmts.

For really advanced analysis, find a topological order of access execution order an iterator over that. (Keep in mind that there is no topological order if there is a loop). Can be rejected in that case. getAccessesInOrder() unfortunately is not advances enough for this.

test/ForwardOpTree/forward_region.ll

10 ↗

(On Diff #113268)

Might be that I wasn't as accurate myself in the old test case that was probably created by myself. Problably started with an undef, but wasn't accepted by ScopDetection.

test/ForwardOpTree/noforward_region.ll

1 ↗

(On Diff #113268)

I just noticed that this was renamed, not deleted. Sorry for the unjustified comment.

However, I think we have no test case for forwarding a load from a region yet, which would be interesting.

[grosser]

It seems the change in collectIncompatibleElts is not even needed. I also have
a hard time to reproduce a test case where the forwarding is refused due to
incompatible statements. Michael, do you have an idea?

[Meinersbur]

Your test cases check that the movement of non-load scalars to/from region works now (Which is amazing!). A test that checks that a load is not forwarded in case there is an (unpredictable) write in a region is missing. It might load the content written the store instead of the original value.

Simplify.cpp markAndSweep needs to know about the prepended instructions. Otherwise it doesn't see their operands and doesn't mark them as used, hence remove them.

include/polly/ScopInfo.h

2369–2370 ↗

(On Diff #113373)

Why this move?

test/ForwardOpTree/forward_into_region.ll

51–57 ↗

(On Diff #113373)

Can you use CHECK: here? We might want to add additional stats which would cause this to break unnecessarily.

test/ForwardOpTree/noforward_from_region.ll

32–35 ↗

(On Diff #113373)

These don't seem to be relevant.

[grosser]

Addressed Michael's comment

The getLI is moved to make it public. It was not public before.

[Meinersbur]

LGTM, I have no more correctness concerns.

In D37298#857643, @grosser wrote:

The getLI is moved to make it public. It was not public before.

I don't see any new uses of it that'd require it to be public.

lib/Support/VirtualInstruction.cpp

186–189 ↗

(On Diff #113396)

This is correct, but did you consider not adding the instruction list instructions as roots? Simplify would be able to remove them and their dependencies if they are not considered roots.

test/ForwardOpTree/forward_from_region.ll

54–59 ↗

(On Diff #113396)

Using CHECK: would make the test less fragile if we want to add more stats.

test/ForwardOpTree/noforward_from_region.ll

3 ↗

(On Diff #113396)

The comment is inaccurate. The load is not moved. Mentioning the reason for this would also be nice.

17 ↗

(On Diff #113396)

Array %B is not used.

33 ↗

(On Diff #113396)

The pseudocode summary says it's A[0] = 42, but this is A[0] = A[0]. I'd prefer the former because it's one less (irrelevant) memory accesses.

polly/trunk/include/polly/ScopInfo.h

public:
 
   /// The range of instructions in this statement.
   iterator_range<std::vector<Instruction *>::const_iterator> insts() const {
     return {insts_begin(), insts_end()};
   }
 
   /// Insert an instruction before all other instructions in this statement.
   void prependInstruction(Instruction *Inst) {
-    assert(isBlockStmt() && "Only block statements support instruction lists");
     Instructions.insert(Instructions.begin(), Inst);
   }
 
   const char *getBaseName() const;
 
   /// Set the isl AST build.
   void setAstBuild(isl::ast_build B) { Build = B; }
 

polly/trunk/lib/Support/VirtualInstruction.cpp

static bool isEscaping(MemoryAccess *MA) {
   Scop *S = MA->getStatement()->getParent();
   return S->isEscaping(cast<Instruction>(MA->getAccessValue()));
 }
 
 /// Add non-removable virtual instructions in @p Stmt to @p RootInsts.
 static void
 addInstructionRoots(ScopStmt *Stmt,
                     SmallVectorImpl<VirtualInstruction> &RootInsts) {
-  // For region statements we must keep all instructions because we do not
-  // support removing instructions from region statements.
   if (!Stmt->isBlockStmt()) {
-    for (auto *BB : Stmt->getRegion()->blocks())
+    // In region statements the terminator statement and all statements that
+    // are not in the entry block cannot be eliminated and consequently must
+    // be roots.
+    RootInsts.emplace_back(Stmt,
+                           Stmt->getRegion()->getEntry()->getTerminator());
+    for (BasicBlock *BB : Stmt->getRegion()->blocks())
+      if (Stmt->getRegion()->getEntry() != BB)
         for (Instruction &Inst : *BB)
           RootInsts.emplace_back(Stmt, &Inst);
     return;
   }
 
   for (Instruction *Inst : Stmt->getInstructions())
     if (isRoot(Inst))
       RootInsts.emplace_back(Stmt, Inst);
 }
 

polly/trunk/lib/Transform/ForwardOpTree.cpp

public:
 
   /// 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) {
-      // Currently we cannot modify the instruction list of region statements.
-      if (!Stmt.isBlockStmt())
-        continue;
-
       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;

polly/trunk/test/ForwardOpTree/forward_from_region.ll

+; RUN: opt %loadPolly -polly-optree -analyze < %s | FileCheck %s -match-full-lines
+;
+; Move instructions from region statements.
+;
+; for (int j = 0; j < n; j += 1) {
+; bodyA:
+;   double val = 21.0 + 21.0;
+;   if (cond)
+;
+; bodyA_true:
+;     A[0] = 42;
+;
+; bodyB:
+;     A[0] = val;
+; }
+;
+define void @func(i32 %n, double* noalias nonnull %A) {
+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 = fadd double 21.0, 21.0
+      %cond = fcmp oeq double 21.0, 21.0
+      br i1 %cond, label %bodyA_true, label %bodyB
+
+    bodyA_true:
+      store double 42.0, double* %A
+      br label %bodyB
+
+    bodyB:
+      store double %val, double* %A
+      br label %bodyB_exit
+
+    bodyB_exit:
+      br label %inc
+
+inc:
+  %j.inc = add nuw nsw i32 %j, 1
+  br label %for
+
+exit:
+  br label %return
+
+return:
+  ret void
+}
+
+; CHECK:      Statistics {
+; CHECK:     Instructions copied: 1
+; CHECK:     Known loads forwarded: 0
+; CHECK:     Read-only accesses copied: 0
+; CHECK:     Operand trees forwarded: 1
+; CHECK:     Statements with forwarded operand trees: 1
+; CHECK: }
+; CHECK: After statements {
+; CHECK:     Stmt_bodyA__TO__bodyB
+; CHECK:             MayWriteAccess :=  [Reduction Type: NONE] [Scalar: 0]
+; CHECK:                 [n] -> { Stmt_bodyA__TO__bodyB[i0] -> MemRef_A[0] };
+; CHECK:             MustWriteAccess := [Reduction Type: NONE] [Scalar: 1]
+; CHECK:                 [n] -> { Stmt_bodyA__TO__bodyB[i0] -> MemRef_val[] };
+; CHECK:             Instructions {
+; CHECK:                   %val = fadd double 2.100000e+01, 2.100000e+01
+; CHECK:                   %cond = fcmp oeq double 2.100000e+01, 2.100000e+01
+; CHECK:             }
+; CHECK:     Stmt_bodyB
+; CHECK:             MustWriteAccess := [Reduction Type: NONE] [Scalar: 0]
+; CHECK:                 [n] -> { Stmt_bodyB[i0] -> MemRef_A[0] };
+; CHECK:             Instructions {
+; CHECK:                   %val = fadd double 2.100000e+01, 2.100000e+01
+; CHECK:                   store double %val, double* %A
+; CHECK:             }
+; CHECK: }
+

polly/trunk/test/ForwardOpTree/forward_into_region.ll

+; RUN: opt %loadPolly -polly-optree -analyze < %s | FileCheck %s -match-full-lines
+;
+; Move instructions to region statements.
+;
+; for (int j = 0; j < n; j += 1) {
+; bodyA:
+;   double val = 21.0 + 21.0;
+;
+; bodyB:
+;   if (cond)
+; body_true:
+;     A[0] = val;
+; }
+;
+define void @func(i32 %n, double* noalias nonnull %A) {
+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 = fadd double 21.0, 21.0
+      br label %bodyB
+
+    bodyB:
+      %cond = fcmp oeq double 21.0, 21.0
+      br i1 %cond, label %bodyB_true, label %bodyB_exit
+
+    bodyB_true:
+      store double %val, double* %A
+      br label %bodyB_exit
+
+    bodyB_exit:
+      br label %inc
+
+inc:
+  %j.inc = add nuw nsw i32 %j, 1
+  br label %for
+
+exit:
+  br label %return
+
+return:
+  ret void
+}
+
+; CHECK: Statistics {
+; CHECK:     Instructions copied: 1
+; CHECK:     Known loads forwarded: 0
+; CHECK:     Read-only accesses copied: 0
+; CHECK:     Operand trees forwarded: 1
+; CHECK:     Statements with forwarded operand trees: 1
+; CHECK: }
+
+; CHECK: After statements {
+; CHECK-NEXT:     Stmt_bodyA
+; CHECK-NEXT:             MustWriteAccess :=  [Reduction Type: NONE] [Scalar: 1]
+; CHECK-NEXT:                 [n] -> { Stmt_bodyA[i0] -> MemRef_val[] };
+; CHECK-NEXT:             Instructions {
+; CHECK-NEXT:                   %val = fadd double 2.100000e+01, 2.100000e+01
+; CHECK-NEXT:             }
+; CHECK-NEXT:     Stmt_bodyB__TO__bodyB_exit
+; CHECK-NEXT:             MayWriteAccess := [Reduction Type: NONE] [Scalar: 0]
+; CHECK-NEXT:                 [n] -> { Stmt_bodyB__TO__bodyB_exit[i0] -> MemRef_A[0] };
+; CHECK-NEXT:             Instructions {
+; CHECK-NEXT:                   %val = fadd double 2.100000e+01, 2.100000e+01
+; CHECK-NEXT:                   %cond = fcmp oeq double 2.100000e+01, 2.100000e+01
+; CHECK-NEXT:             }
+; CHECK-NEXT: }

polly/trunk/test/ForwardOpTree/noforward_from_region.ll

+; RUN: opt %loadPolly -polly-optree -analyze < %s | FileCheck %s -match-full-lines
+;
+; Ensure we do not move instructions from region statements in case the
+; instruction to move loads from an array which is also written to from
+; within the region. This is necessary as complex region statements may prevent
+; us from detecting possible memory conflicts.
+;
+; for (int j = 0; j < n; j += 1) {
+; bodyA:
+;   double val = A[0];
+;   if (cond)
+;
+; bodyA_true:
+;     A[0] = 42;
+;
+; bodyB:
+;     A[0] = val;
+; }
+;
+define void @func(i32 %n, double* noalias nonnull %A) {
+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 = load double, double* %A
+      %cond = fcmp oeq double 21.0, 21.0
+      br i1 %cond, label %bodyA_true, label %bodyB
+
+    bodyA_true:
+      store double 42.0, double* %A
+      br label %bodyB
+
+    bodyB:
+      store double %val, double* %A
+      br label %bodyB_exit
+
+    bodyB_exit:
+      br label %inc
+
+inc:
+  %j.inc = add nuw nsw i32 %j, 1
+  br label %for
+
+exit:
+  br label %return
+
+return:
+  ret void
+}
+
+; CHECK: ForwardOpTree executed, but did not modify anything

polly/trunk/test/ForwardOpTree/noforward_region.ll

-; RUN: opt %loadPolly -polly-optree -analyze < %s | FileCheck %s -match-full-lines
-;
-; Do not move instructions to region statements.
-;
-; for (int j = 0; j < n; j += 1) {
-; bodyA:
-;   double val = 21.0 + 21.0;
-;
-; bodyB_entry:
-;   if (undef)
-; body_true:
-;     A[0] = val;
-; }
-;
-define void @func(i32 %n, double* noalias nonnull %A) {
-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 = fadd double 21.0, 21.0
-      br label %bodyB
-
-    bodyB:
-      %cond = fcmp oeq double 21.0, 21.0
-      br i1 %cond, label %bodyB_true, label %bodyB_exit
-
-    bodyB_true:
-      store double %val, double* %A
-      br label %bodyB_exit
-
-    bodyB_exit:
-      br label %inc
-
-inc:
-  %j.inc = add nuw nsw i32 %j, 1
-  br label %for
-
-exit:
-  br label %return
-
-return:
-  ret void
-}
-
-
-; CHECK: ForwardOpTree executed, but did not modify anything