summaryrefslogtreecommitdiffstats
diff options
context:
space:
mode:
Diffstat
-rw-r--r--polly/include/polly/ForwardOpTree.h28
-rw-r--r--polly/include/polly/ScopInfo.h6
-rw-r--r--polly/lib/CMakeLists.txt1
-rw-r--r--polly/lib/Support/RegisterPasses.cpp9
-rw-r--r--polly/lib/Transform/ForwardOpTree.cpp356
-rw-r--r--polly/test/ForwardOpTree/forward_instruction.ll62
-rw-r--r--polly/test/ForwardOpTree/forward_transitive.ll77
-rw-r--r--polly/test/ForwardOpTree/noforward_partial.ll48
-rw-r--r--polly/test/ForwardOpTree/noforward_phi.ll42
-rw-r--r--polly/test/ForwardOpTree/noforward_region.ll51
-rw-r--r--polly/test/ForwardOpTree/noforward_sideffects.ll46
-rw-r--r--polly/test/ForwardOpTree/noforward_synthesizable.ll43
12 files changed, 769 insertions, 0 deletions
diff --git a/polly/include/polly/ForwardOpTree.h b/polly/include/polly/ForwardOpTree.h
new file mode 100644
index 00000000000..f2f0becefdd
--- /dev/null
+++ b/polly/include/polly/ForwardOpTree.h
@@ -0,0 +1,28 @@
+//===------ 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 */
diff --git a/polly/include/polly/ScopInfo.h b/polly/include/polly/ScopInfo.h
index 094b9f5278c..7b6c5074370 100644
--- a/polly/include/polly/ScopInfo.h
+++ b/polly/include/polly/ScopInfo.h
@@ -1591,6 +1591,12 @@ public:
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.
diff --git a/polly/lib/CMakeLists.txt b/polly/lib/CMakeLists.txt
index 1141de539c2..e41a20c097f 100644
--- a/polly/lib/CMakeLists.txt
+++ b/polly/lib/CMakeLists.txt
@@ -58,6 +58,7 @@ add_library(PollyCore OBJECT
Transform/ScheduleOptimizer.cpp
Transform/FlattenSchedule.cpp
Transform/FlattenAlgo.cpp
+ Transform/ForwardOpTree.cpp
Transform/DeLICM.cpp
Transform/Simplify.cpp
${POLLY_HEADER_FILES}
diff --git a/polly/lib/Support/RegisterPasses.cpp b/polly/lib/Support/RegisterPasses.cpp
index bd01a269d24..66199de797e 100644
--- a/polly/lib/Support/RegisterPasses.cpp
+++ b/polly/lib/Support/RegisterPasses.cpp
@@ -27,6 +27,7 @@
#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"
@@ -188,6 +189,11 @@ static cl::opt<bool>
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\""),
@@ -250,6 +256,7 @@ void initializePollyPasses(PassRegistry &Registry) {
initializeScopInfoWrapperPassPass(Registry);
initializeCodegenCleanupPass(Registry);
initializeFlattenSchedulePass(Registry);
+ initializeForwardOpTreePass(Registry);
initializeDeLICMPass(Registry);
initializeSimplifyPass(Registry);
initializeDumpModulePass(Registry);
@@ -306,6 +313,8 @@ void registerPollyPasses(llvm::legacy::PassManagerBase &PM) {
if (EnablePolyhedralInfo)
PM.add(polly::createPolyhedralInfoPass());
+ if (EnableForwardOpTree)
+ PM.add(polly::createForwardOpTreePass());
if (EnableDeLICM)
PM.add(polly::createDeLICMPass());
if (EnableSimplify)
diff --git a/polly/lib/Transform/ForwardOpTree.cpp b/polly/lib/Transform/ForwardOpTree.cpp
new file mode 100644
index 00000000000..f4336394ed6
--- /dev/null
+++ b/polly/lib/Transform/ForwardOpTree.cpp
@@ -0,0 +1,356 @@
+//===------ 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 the 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
+/// increases 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)
diff --git a/polly/test/ForwardOpTree/forward_instruction.ll b/polly/test/ForwardOpTree/forward_instruction.ll
new file mode 100644
index 00000000000..4180ca231b6
--- /dev/null
+++ b/polly/test/ForwardOpTree/forward_instruction.ll
@@ -0,0 +1,62 @@
+; 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: }
diff --git a/polly/test/ForwardOpTree/forward_transitive.ll b/polly/test/ForwardOpTree/forward_transitive.ll
new file mode 100644
index 00000000000..b45b4662116
--- /dev/null
+++ b/polly/test/ForwardOpTree/forward_transitive.ll
@@ -0,0 +1,77 @@
+; 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: }
diff --git a/polly/test/ForwardOpTree/noforward_partial.ll b/polly/test/ForwardOpTree/noforward_partial.ll
new file mode 100644
index 00000000000..ac49266b825
--- /dev/null
+++ b/polly/test/ForwardOpTree/noforward_partial.ll
@@ -0,0 +1,48 @@
+; 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
diff --git a/polly/test/ForwardOpTree/noforward_phi.ll b/polly/test/ForwardOpTree/noforward_phi.ll
new file mode 100644
index 00000000000..ccdf6c7c0f2
--- /dev/null
+++ b/polly/test/ForwardOpTree/noforward_phi.ll
@@ -0,0 +1,42 @@
+; 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
diff --git a/polly/test/ForwardOpTree/noforward_region.ll b/polly/test/ForwardOpTree/noforward_region.ll
new file mode 100644
index 00000000000..b32aef3dbeb
--- /dev/null
+++ b/polly/test/ForwardOpTree/noforward_region.ll
@@ -0,0 +1,51 @@
+; 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
diff --git a/polly/test/ForwardOpTree/noforward_sideffects.ll b/polly/test/ForwardOpTree/noforward_sideffects.ll
new file mode 100644
index 00000000000..6a688085018
--- /dev/null
+++ b/polly/test/ForwardOpTree/noforward_sideffects.ll
@@ -0,0 +1,46 @@
+; 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
diff --git a/polly/test/ForwardOpTree/noforward_synthesizable.ll b/polly/test/ForwardOpTree/noforward_synthesizable.ll
new file mode 100644
index 00000000000..593a7029829
--- /dev/null
+++ b/polly/test/ForwardOpTree/noforward_synthesizable.ll
@@ -0,0 +1,43 @@
+; 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
OpenPOWER on IntegriCloud