[ForwardOpTree] Introduce the -polly-optree pass.

[Meinersbur]

Summary

This pass 'forwards' operand trees into statements that use them in order to avoid scalar dependencies.

This minimal implementation handles only the case of speculatable instructions. We will successively add support for:

• Hoisted loads
• Read-only values
• Synthesizable values
• Loads
• PHIs
• Forwarding only parts of the tree

[grosser]

lib/Transform/ForwardOpTree.cpp

47

and ALL THE operand tree

[grosser]

One more typo.

lib/Transform/ForwardOpTree.cpp

296

increases

[nandini12396]

Could you please explain what is the meaning of 'forwarding' of operand trees?

polly/trunk/include/polly/ScopInfo.h

1595 ↗

(On Diff #107785)

*Instruction

[bollu]

polly/trunk/lib/Transform/ForwardOpTree.cpp

108 ↗

(On Diff #107785)

@Meinersbur - Is the comment incorrect?

When DoIt == true, does it not return FD_DidForward / FD_DidNotFowrard

And when DoIt == false, it returns FD_CanForward ?

I am basing this off of this piece of code:

snippet-with-do-it-returns.cpp

if (DoIt)
  return FD_DidForward;
return FD_CanForward;

[Meinersbur]

In D35754#818516, @nandini12396 wrote:

Could you please explain what is the meaning of 'forwarding' of operand trees?

Suppose you have two statements:

StmtA:
  %add = fadd double 21.0,21.0
  bl label %StmtB

StmtB:
  store double %add, double*A

This would induce a scalar dependency from %StmtA to %StmtB. To avoid, we can recompute %add in %StmtB instead:

StmtA:
  %add = fadd double 21.0,21.0
  bl label %StmtB

StmtB:
  %add_ = fadd double 21.0,21.0
  store double %add_, double*A

This "forwards" %add (and its operand tree/DAG) to StmtB.

I am open to naming it differently. I considered "reverse code motion".

polly/trunk/include/polly/ScopInfo.h

1595 ↗

(On Diff #107785)

Thanks.

[nandini12396]

In D35754#818793, @Meinersbur wrote:

In D35754#818516, @nandini12396 wrote:

Could you please explain what is the meaning of 'forwarding' of operand trees?

Suppose you have two statements:

StmtA:
  %add = fadd double 21.0,21.0
  bl label %StmtB

StmtB:
  store double %add, double*A

This would induce a scalar dependency from %StmtA to %StmtB. To avoid, we can recompute %add in %StmtB instead:

StmtA:
  %add = fadd double 21.0,21.0
  bl label %StmtB

StmtB:
  %add_ = fadd double 21.0,21.0
  store double %add_, double*A

This "forwards" %add (and its operand tree/DAG) to StmtB.

Thank you. This is really nice idea. Do you have some cost modeling for when to allow this forwarding?

I am open to naming it differently. I considered "reverse code motion".

[Meinersbur]

In D35754#818836, @nandini12396 wrote:

Thank you. This is really nice idea. Do you have some cost modeling for when to allow this forwarding?

There is no cost modeling (yet), it is assumed to be always beneficial. The GVN pass should later be able do remove instruction duplication and move them back to cheaper places again.

include/polly/ForwardOpTree.h

+//===------ ForwardOpTree.h -------------------------------------*- C++ -*-===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+//
+// Move instructions between statements.
+//
+//===----------------------------------------------------------------------===//
+
+#ifndef POLLY_FORWARDOPTREE_H
+#define POLLY_FORWARDOPTREE_H
+
+namespace polly {
+class ScopPass;
+
+ScopPass *createForwardOpTreePass();
+} // namespace polly
+
+namespace llvm {
+class PassRegistry;
+void initializeForwardOpTreePass(llvm::PassRegistry &);
+} // namespace llvm
+
+#endif /* POLLY_FORWARDOPTREE_H */

include/polly/ScopInfo.h

public:
   }
 
   /// The range of instructions in this statement.
   llvm::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 prependInstrunction(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_keep isl_ast_build *B) { Build = B; }
 
   /// Get the isl AST build.
   __isl_keep isl_ast_build *getAstBuild() const { return Build; }
 

lib/CMakeLists.txt

add_library(PollyCore OBJECT
   Support/VirtualInstruction.cpp
   ${POLLY_JSON_FILES}
   Transform/Canonicalization.cpp
   Transform/CodePreparation.cpp
   Transform/DeadCodeElimination.cpp
   Transform/ScheduleOptimizer.cpp
   Transform/FlattenSchedule.cpp
   Transform/FlattenAlgo.cpp
+  Transform/ForwardOpTree.cpp
   Transform/DeLICM.cpp
   Transform/Simplify.cpp
   ${POLLY_HEADER_FILES}
   )
 set_target_properties(PollyCore PROPERTIES FOLDER "Polly")
 
 # Create the library that can be linked into LLVM's tools and Polly's unittests.
 # It depends on all library it needs, such that with

lib/Support/RegisterPasses.cpp

 #include "polly/RegisterPasses.h"
 #include "polly/Canonicalization.h"
 #include "polly/CodeGen/CodeGeneration.h"
 #include "polly/CodeGen/CodegenCleanup.h"
 #include "polly/CodeGen/PPCGCodeGeneration.h"
 #include "polly/DeLICM.h"
 #include "polly/DependenceInfo.h"
 #include "polly/FlattenSchedule.h"
+#include "polly/ForwardOpTree.h"
 #include "polly/LinkAllPasses.h"
 #include "polly/Options.h"
 #include "polly/PolyhedralInfo.h"
 #include "polly/ScopDetection.h"
 #include "polly/ScopInfo.h"
 #include "polly/Simplify.h"
 #include "polly/Support/DumpModulePass.h"
 #include "llvm/Analysis/CFGPrinter.h"
CFGPrinter("polly-view-cfg",
                cl::Hidden, cl::init(false), cl::cat(PollyCategory));
 
 static cl::opt<bool>
     EnablePolyhedralInfo("polly-enable-polyhedralinfo",
                          cl::desc("Enable polyhedral interface of Polly"),
                          cl::Hidden, cl::init(false), cl::cat(PollyCategory));
 
 static cl::opt<bool>
+    EnableForwardOpTree("polly-enable-optree",
+                        cl::desc("Enable operand tree forwarding"), cl::Hidden,
+                        cl::init(false), cl::cat(PollyCategory));
+
+static cl::opt<bool>
     DumpBefore("polly-dump-before",
                cl::desc("Dump module before Polly transformations into a file "
                         "suffixed with \"-before\""),
                cl::init(false), cl::cat(PollyCategory));
 
 static cl::list<std::string> DumpBeforeFile(
     "polly-dump-before-file",
     cl::desc("Dump module before Polly transformations to the given file"),
#endif
   initializeIslScheduleOptimizerPass(Registry);
   initializePollyCanonicalizePass(Registry);
   initializePolyhedralInfoPass(Registry);
   initializeScopDetectionWrapperPassPass(Registry);
   initializeScopInfoRegionPassPass(Registry);
   initializeScopInfoWrapperPassPass(Registry);
   initializeCodegenCleanupPass(Registry);
   initializeFlattenSchedulePass(Registry);
+  initializeForwardOpTreePass(Registry);
   initializeDeLICMPass(Registry);
   initializeSimplifyPass(Registry);
   initializeDumpModulePass(Registry);
   initializePruneUnprofitablePass(Registry);
 }
 
 /// Register Polly passes such that they form a polyhedral optimizer.
 ///
if (PollyPrinter)
     PM.add(polly::createDOTPrinterPass());
   if (PollyOnlyPrinter)
     PM.add(polly::createDOTOnlyPrinterPass());
 
   PM.add(polly::createScopInfoRegionPassPass());
   if (EnablePolyhedralInfo)
     PM.add(polly::createPolyhedralInfoPass());
 
+  if (EnableForwardOpTree)
+    PM.add(polly::createForwardOpTreePass());
   if (EnableDeLICM)
     PM.add(polly::createDeLICMPass());
   if (EnableSimplify)
     PM.add(polly::createSimplifyPass());
 
   if (ImportJScop)
     PM.add(polly::createJSONImporterPass());
 

lib/Transform/ForwardOpTree.cpp

+//===------ ForwardOpTree.h -------------------------------------*- C++ -*-===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+//
+// Move instructions between statements.
+//
+//===----------------------------------------------------------------------===//
+
+#include "polly/ForwardOpTree.h"
+
+#include "polly/ScopInfo.h"
+#include "polly/ScopPass.h"
+#include "polly/Support/GICHelper.h"
+#include "polly/Support/VirtualInstruction.h"
+#include "llvm/Analysis/ValueTracking.h"
+
+#define DEBUG_TYPE "polly-delicm"
+
+using namespace polly;
+using namespace llvm;
+
+STATISTIC(TotalInstructionsCopied, "Number of copied instructions");
+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");
+
+namespace {
+
+/// The state of whether an operand tree was/can be forwarded.
+enum ForwardingDecision {
+  FD_CannotForward,
+  FD_CanForward,
+  FD_DidForward,
+};
+
+/// Implementation of operand tree forwarding for a specific SCoP.
+///
+/// For a statement that requires a scalar value (through a value read
+/// MemoryAccess), see if its operand can be moved into the statement. If so,
+/// the MemoryAccess is removed and the all operand tree instructions are moved
+/// into the statement. All original instructions are left in the source
+/// statements. The simplification pass can clean these up.
+class ForwardOpTreeImpl {
+private:
+  /// The SCoP we are currently processing.
+  Scop *S;
+
+  /// LoopInfo is required for VirtualUse.
+  LoopInfo *LI;
+
+  /// How many instructions have been copied to other statements.
+  int NumInstructionsCopied = 0;
+
+  /// How many operand trees have been forwarded.
+  int NumForwardedTrees = 0;
+
+  /// Number of statements with at least one forwarded operand tree.
+  int NumModifiedStmts = 0;
+
+  /// Whether we carried out at least one change to the SCoP.
+  bool Modified = false;
+
+  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) << "Operand trees forwarded: " << NumForwardedTrees
+                          << '\n';
+    OS.indent(Indent + 4) << "Statements with forwarded operand trees: "
+                          << NumModifiedStmts << '\n';
+    OS.indent(Indent) << "}\n";
+  }
+
+  void printStatements(llvm::raw_ostream &OS, int Indent = 0) const {
+    OS.indent(Indent) << "After statements {\n";
+    for (auto &Stmt : *S) {
+      OS.indent(Indent + 4) << Stmt.getBaseName() << "\n";
+      for (auto *MA : Stmt)
+        MA->print(OS);
+
+      OS.indent(Indent + 12);
+      Stmt.printInstructions(OS);
+    }
+    OS.indent(Indent) << "}\n";
+  }
+
+  /// 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 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 When DoIt==true, return whether the operand tree can be forwarded.
+  ///         When DoIt==false, return FD_DidForward.
+  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:
+    case VirtualUse::Block:
+      // These can be used anywhere without special considerations.
+      if (DoIt)
+        return FD_DidForward;
+      return FD_CanForward;
+
+    case VirtualUse::Synthesizable:
+      // Not supported yet.
+      DEBUG(dbgs() << "    Cannot forward synthesizable: " << *UseVal << "\n");
+      return FD_CannotForward;
+
+    case VirtualUse::Hoisted:
+      // Not supported yet.
+      DEBUG(dbgs() << "    Cannot forward hoisted load: " << *UseVal << "\n");
+      return FD_CannotForward;
+
+    case VirtualUse::ReadOnly:
+      // Not supported yet.
+      DEBUG(dbgs() << "    Cannot forward read-only val: " << *UseVal << "\n");
+      return FD_CannotForward;
+
+    case VirtualUse::Intra:
+    case VirtualUse::Inter:
+      auto Inst = cast<Instruction>(UseVal);
+
+      // 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)
+      // 3. Not cause undefined behaviour (we might copy to a location when the
+      // original instruction was no executed; this is currently not possible
+      // because we do not forward PHINodes)
+      // 4. Not leak memory if executed multiple times (I am looking at you,
+      // malloc!)
+      //
+      // Instruction::mayHaveSideEffects is not sufficient because it considers
+      // malloc to not have side-effects. llvm::isSafeToSpeculativelyExecute is
+      // not sufficient because it allows memory accesses.
+      if (mayBeMemoryDependent(*Inst)) {
+        DEBUG(dbgs() << "    Cannot forward side-effect instruction: " << *Inst
+                     << "\n");
+        return FD_CannotForward;
+      }
+
+      Loop *DefLoop = LI->getLoopFor(Inst->getParent());
+      ScopStmt *DefStmt = S->getStmtFor(Inst);
+      assert(DefStmt && "Value must be defined somewhere");
+
+      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->prependInstrunction(Inst);
+        NumInstructionsCopied++;
+        TotalInstructionsCopied++;
+      }
+
+      for (Value *OpVal : Inst->operand_values()) {
+        ForwardingDecision OpDecision =
+            canForwardTree(TargetStmt, OpVal, DefStmt, DefLoop, DoIt);
+        switch (OpDecision) {
+        case FD_CannotForward:
+          assert(!DoIt);
+          return FD_CannotForward;
+
+        case FD_CanForward:
+          assert(!DoIt);
+          break;
+
+        case FD_DidForward:
+          assert(DoIt);
+          break;
+        }
+      }
+
+      if (DoIt)
+        return FD_DidForward;
+      return FD_CanForward;
+    }
+
+    llvm_unreachable("Case unhandled");
+  }
+
+  /// Try to forward an operand tree rooted in @p RA.
+  bool tryForwardTree(MemoryAccess *RA) {
+    assert(RA->isLatestScalarKind());
+    DEBUG(dbgs() << "Trying to forward operand tree " << RA << "...\n");
+
+    ScopStmt *Stmt = RA->getStatement();
+    Loop *InLoop = Stmt->getSurroundingLoop();
+
+    ForwardingDecision Assessment =
+        canForwardTree(Stmt, RA->getAccessValue(), Stmt, InLoop, false);
+    assert(Assessment != FD_DidForward);
+    if (Assessment == FD_CannotForward)
+      return false;
+
+    ForwardingDecision Execution =
+        canForwardTree(Stmt, RA->getAccessValue(), Stmt, InLoop, true);
+    assert(Execution == FD_DidForward);
+
+    Stmt->removeSingleMemoryAccess(RA);
+    return true;
+  }
+
+public:
+  ForwardOpTreeImpl(Scop *S, LoopInfo *LI) : S(S), LI(LI) {}
+
+  /// 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;
+        if (!RA->isLatestScalarKind())
+          continue;
+
+        Accs.push_back(RA);
+      }
+
+      for (MemoryAccess *RA : Accs) {
+        if (tryForwardTree(RA)) {
+          Modified = true;
+          StmtModified = true;
+          NumForwardedTrees++;
+          TotalForwardedTrees++;
+        }
+      }
+
+      if (StmtModified) {
+        NumModifiedStmts++;
+        TotalModifiedStmts++;
+      }
+    }
+
+    if (Modified)
+      ScopsModified++;
+    return Modified;
+  }
+
+  /// Print the pass result, performed transformations and the SCoP after the
+  /// transformation.
+  void print(llvm::raw_ostream &OS, int Indent = 0) {
+    printStatistics(OS, Indent);
+
+    if (!Modified) {
+      // This line can easily be checked in regression tests.
+      OS << "ForwardOpTree executed, but did not modify anything\n";
+      return;
+    }
+
+    printStatements(OS, Indent);
+  }
+};
+
+/// Pass that redirects scalar reads to array elements that are known to contain
+/// the same value.
+///
+/// This reduces the number of scalar accesses and therefore potentially
+/// increased the freedom of the scheduler. In the ideal case, all reads of a
+/// scalar definition are redirected (We currently do not care about removing
+/// the write in this case).  This is also useful for the main DeLICM pass as
+/// there are less scalars to be mapped.
+class ForwardOpTree : public ScopPass {
+private:
+  ForwardOpTree(const ForwardOpTree &) = delete;
+  const ForwardOpTree &operator=(const ForwardOpTree &) = delete;
+
+  /// The pass implementation, also holding per-scop data.
+  std::unique_ptr<ForwardOpTreeImpl> Impl;
+
+public:
+  static char ID;
+
+  explicit ForwardOpTree() : ScopPass(ID) {}
+
+  virtual void getAnalysisUsage(AnalysisUsage &AU) const override {
+    AU.addRequiredTransitive<ScopInfoRegionPass>();
+    AU.addRequired<LoopInfoWrapperPass>();
+    AU.setPreservesAll();
+  }
+
+  virtual bool runOnScop(Scop &S) override {
+    // Free resources for previous SCoP's computation, if not yet done.
+    releaseMemory();
+
+    LoopInfo &LI = getAnalysis<LoopInfoWrapperPass>().getLoopInfo();
+    Impl = make_unique<ForwardOpTreeImpl>(&S, &LI);
+
+    DEBUG(dbgs() << "Forwarding operand trees...\n");
+    Impl->forwardOperandTrees();
+
+    DEBUG(dbgs() << "\nFinal Scop:\n");
+    DEBUG(dbgs() << S);
+
+    return false;
+  }
+
+  virtual void printScop(raw_ostream &OS, Scop &S) const override {
+    if (!Impl)
+      return;
+
+    assert(Impl->getScop() == &S);
+    Impl->print(OS);
+  }
+
+  virtual void releaseMemory() override { Impl.reset(); }
+
+}; // class ForwardOpTree
+
+char ForwardOpTree::ID;
+} // anonymous namespace
+
+ScopPass *polly::createForwardOpTreePass() { return new ForwardOpTree(); }
+
+INITIALIZE_PASS_BEGIN(ForwardOpTree, "polly-optree",
+                      "Polly - Forward operand tree", false, false)
+INITIALIZE_PASS_DEPENDENCY(LoopInfoWrapperPass)
+INITIALIZE_PASS_END(ForwardOpTree, "polly-optree",
+                    "Polly - Forward operand tree", false, false)

test/ForwardOpTree/forward_instruction.ll

+; RUN: opt %loadPolly -polly-optree -analyze < %s | FileCheck %s -match-full-lines
+;
+; Move %val to %bodyB, so %bodyA can be removed (by -polly-simplify)
+;
+; for (int j = 0; j < n; j += 1) {
+; bodyA:
+;   double val = 21.0 + 21.0;
+;
+; 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
+      br label %bodyB
+
+    bodyB:
+      store double %val, double* %A
+      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:     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
+; CHECK-NEXT:             MustWriteAccess :=  [Reduction Type: NONE] [Scalar: 0]
+; CHECK-NEXT:                 [n] -> { Stmt_bodyB[i0] -> MemRef_A[0] };
+; CHECK-NEXT:             Instructions {
+; CHECK-NEXT:                   %val = fadd double 2.100000e+01, 2.100000e+01
+; CHECK-NEXT:                   store double %val, double* %A
+; CHECK-NEXT:             }
+; CHECK-NEXT: }

test/ForwardOpTree/forward_transitive.ll

+; RUN: opt %loadPolly -polly-optree -analyze < %s | FileCheck %s -match-full-lines
+;
+; Move %v and %val to %bodyB, so %bodyA can be removed (by -polly-simplify)
+;
+; for (int j = 0; j < n; j += 1) {
+; bodyA:
+;   double val1 = 12.5 + 12.5;
+;
+; bodyB:
+;   double val2 = 21.0 + 21.0;
+;
+; bodyC:
+;   A[0] = val2;
+; }
+;
+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:
+      %val1 = fadd double 12.5, 12.5
+      br label %bodyB
+      
+    bodyB:
+      %val2 = fadd double %val1, 21.0
+      br label %bodyC
+
+    bodyC:
+      store double %val2, double* %A
+      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: 3
+; CHECK:     Operand trees forwarded: 2
+; CHECK:     Statements with forwarded operand trees: 2
+; CHECK: }
+
+; CHECK:      After statements {
+; CHECK-NEXT:     Stmt_bodyA
+; CHECK-NEXT:             MustWriteAccess :=  [Reduction Type: NONE] [Scalar: 1]
+; CHECK-NEXT:                 [n] -> { Stmt_bodyA[i0] -> MemRef_val1[] };
+; CHECK-NEXT:             Instructions {
+; CHECK-NEXT:                   %val1 = fadd double 1.250000e+01, 1.250000e+01
+; CHECK-NEXT:             }
+; CHECK-NEXT:     Stmt_bodyB
+; CHECK-NEXT:             MustWriteAccess :=  [Reduction Type: NONE] [Scalar: 1]
+; CHECK-NEXT:                 [n] -> { Stmt_bodyB[i0] -> MemRef_val2[] };
+; CHECK-NEXT:             Instructions {
+; CHECK-NEXT:                   %val1 = fadd double 1.250000e+01, 1.250000e+01
+; CHECK-NEXT:                   %val2 = fadd double %val1, 2.100000e+01
+; CHECK-NEXT:             }
+; CHECK-NEXT:     Stmt_bodyC
+; CHECK-NEXT:             MustWriteAccess :=  [Reduction Type: NONE] [Scalar: 0]
+; CHECK-NEXT:                 [n] -> { Stmt_bodyC[i0] -> MemRef_A[0] };
+; CHECK-NEXT:             Instructions {
+; CHECK-NEXT:                   %val1 = fadd double 1.250000e+01, 1.250000e+01
+; CHECK-NEXT:                   %val2 = fadd double %val1, 2.100000e+01
+; CHECK-NEXT:                   store double %val2, double* %A
+; CHECK-NEXT:             }
+; CHECK-NEXT: }

test/ForwardOpTree/noforward_partial.ll

+; RUN: opt %loadPolly -polly-optree -analyze < %s | FileCheck %s -match-full-lines
+;
+; Not the entire operand tree can be forwarded,
+; some scalar dependencies would remain.
+;
+; for (int j = 0; j < n; j += 1) {
+; bodyA:
+;   double val = f() + 21.0;
+;
+; bodyB:
+;   A[0] = val;
+; }
+;
+declare double @f(...) #1
+
+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:
+      %v = call double (...) @f()
+      %val = fadd double %v, 21.0
+      br label %bodyB
+
+    bodyB:
+      store double %val, double* %A
+      br label %inc
+
+inc:
+  %j.inc = add nuw nsw i32 %j, 1
+  br label %for
+
+exit:
+  br label %return
+
+return:
+  ret void
+}
+
+attributes #1 = { nounwind readnone }
+
+
+; CHECK: ForwardOpTree executed, but did not modify anything

test/ForwardOpTree/noforward_phi.ll

+; RUN: opt %loadPolly -polly-optree -analyze < %s | FileCheck %s -match-full-lines
+;
+; Do not move PHI nodes.
+;
+; for (int j = 0; j < n; j += 1) {
+; bodyA:
+;   double val = 42.0;
+;
+; 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 =  phi double [42.0, %for]
+      br label %bodyB
+
+    bodyB:
+      store double %val, double* %A
+      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

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

test/ForwardOpTree/noforward_sideffects.ll

+; RUN: opt %loadPolly  -polly-optree -analyze < %s | FileCheck %s -match-full-lines
+;
+; Do not forward instructions with side-effects (here: function call).
+;
+; for (int j = 0; j < n; j += 1) {
+; bodyA:
+;   double val = f();
+;
+; bodyB:
+;   A[0] = val;
+; }
+;
+declare double @f(double* %A) #1
+
+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 = call double (double*) @f(double* %A)
+      br label %bodyB
+
+    bodyB:
+      store double %val, double* %A
+      br label %inc
+
+inc:
+  %j.inc = add nuw nsw i32 %j, 1
+  br label %for
+
+exit:
+  br label %return
+
+return:
+  ret void
+}
+
+attributes #1 = { nounwind readnone }
+
+
+; CHECK: ForwardOpTree executed, but did not modify anything

test/ForwardOpTree/noforward_synthesizable.ll

+; RUN: opt %loadPolly -polly-optree -analyze < %s | FileCheck %s -match-full-lines
+;
+; %val has a synthesizable argument that we currently do not support.
+;
+; for (int j = 0; j < n; j += 1) {
+; bodyA:
+;   double v = j;
+;   double val = 21.0 + 21.0;
+;
+; 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 = sitofp i32 %j to double         
+      br label %bodyB
+
+    bodyB:
+      store double %val, double* %A
+      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