[ForwardOpTree] Support synthesizable values.

This allows -polly-optree to move instructions that depend on
synthesizable values.

The difficulty for synthesizable values is that their value depends on
the location. When it is moved over a loop header, and the SCEV
expression depends on the loop induction variable (SCEVAddRecExpr), it
would use the current induction variable instead of the last one.

At the moment we cannot forward PHI nodes such that crossing the header
of loops referenced by SCEVAddRecExpr is not possible (assuming the loop
header has at least two incoming blocks: for entering the loop and the
backedge, such any instruction to be forwarded must have a phi between
use and definition).

A remaining issue is when the forwarded value is used after the loop,
but is only synthesizable inside the loop. This happens e.g. if
ScalarEvolution is unable to determine the number of loop iterations or
the initial loop value. We do not forward in this situation.

Differential Revision: https://reviews.llvm.org/D36102

llvm-svn: 309609

1 files changed, 30 insertions, 10 deletions

diff --git a/polly/lib/Transform/ForwardOpTree.cpp b/polly/lib/Transform/ForwardOpTree.cpp
index 81ace39b8de..852fc188542 100644
--- a/polly/lib/Transform/ForwardOpTree.cpp
+++ b/polly/lib/Transform/ForwardOpTree.cpp
@@ -140,13 +140,6 @@ private:
   ForwardingDecision canForwardTree(ScopStmt *TargetStmt, Value *UseVal,
                                     ScopStmt *UseStmt, Loop *UseLoop,
                                     bool DoIt) {
-
-    // PHis are not yet supported.
-    if (isa<PHINode>(UseVal)) {
-      DEBUG(dbgs() << "    Cannot forward PHI: " << *UseVal << "\n");
-      return FD_CannotForward;
-    }
-
     VirtualUse VUse = VirtualUse::create(UseStmt, UseLoop, UseVal, true);
     switch (VUse.getKind()) {
     case VirtualUse::Constant:
@@ -157,10 +150,31 @@ private:
         return FD_DidForward;
       return FD_CanForwardLeaf;
 
-    case VirtualUse::Synthesizable:
-      // Not supported yet.
-      DEBUG(dbgs() << "    Cannot forward synthesizable: " << *UseVal << "\n");
+    case VirtualUse::Synthesizable: {
+      // ScopExpander will take care for of generating the code at the new
+      // location.
+      if (DoIt)
+        return FD_DidForward;
+
+      // 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
+      // do not allow forwarding PHI nodes, thus this should never occur (the
+      // only exception where no phi is necessary being an unreachable loop
+      // without edge from the outside).
+      VirtualUse TargetUse = VirtualUse::create(
+          S, TargetStmt, TargetStmt->getSurroundingLoop(), UseVal, true);
+      if (TargetUse.getKind() == VirtualUse::Synthesizable)
+        return FD_CanForwardLeaf;
+
+      DEBUG(dbgs() << "    Synthesizable would not be synthesizable anymore: "
+                   << *UseVal << "\n");
       return FD_CannotForward;
+    }
 
     case VirtualUse::ReadOnly:
       // Note that we cannot return FD_CanForwardTree here. With a operand tree
@@ -185,6 +199,12 @@ private:
     case VirtualUse::Inter:
       auto Inst = cast<Instruction>(UseVal);
 
+      // PHIs, unless synthesizable, are not yet supported.
+      if (isa<PHINode>(Inst)) {
+        DEBUG(dbgs() << "    Cannot forward PHI: " << *UseVal << "\n");
+        return FD_CannotForward;
+      }
+
       // Compatible instructions must satisfy the following conditions:
       // 1. Idempotent (instruction will be copied, not moved; although its
       //    original instance might be removed by simplification)