diff options
| -rw-r--r-- | polly/include/polly/ScopInfo.h | 1 | ||||
| -rw-r--r-- | polly/lib/Support/VirtualInstruction.cpp | 14 | ||||
| -rw-r--r-- | polly/lib/Transform/ForwardOpTree.cpp | 4 | ||||
| -rw-r--r-- | polly/test/ForwardOpTree/forward_from_region.ll | 78 | ||||
| -rw-r--r-- | polly/test/ForwardOpTree/forward_into_region.ll | 72 | ||||
| -rw-r--r-- | polly/test/ForwardOpTree/noforward_from_region.ll (renamed from polly/test/ForwardOpTree/noforward_region.ll) | 27 |
6 files changed, 175 insertions, 21 deletions
diff --git a/polly/include/polly/ScopInfo.h b/polly/include/polly/ScopInfo.h index 44f307827cb..b8cb90c8202 100644 --- a/polly/include/polly/ScopInfo.h +++ b/polly/include/polly/ScopInfo.h @@ -1601,7 +1601,6 @@ public: /// 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); } diff --git a/polly/lib/Support/VirtualInstruction.cpp b/polly/lib/Support/VirtualInstruction.cpp index 614ea9243d9..036236afb49 100644 --- a/polly/lib/Support/VirtualInstruction.cpp +++ b/polly/lib/Support/VirtualInstruction.cpp @@ -180,12 +180,16 @@ static bool isEscaping(MemoryAccess *MA) { 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()) - for (Instruction &Inst : *BB) - RootInsts.emplace_back(Stmt, &Inst); + // 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; } diff --git a/polly/lib/Transform/ForwardOpTree.cpp b/polly/lib/Transform/ForwardOpTree.cpp index db6756decf3..dffd3cb1d55 100644 --- a/polly/lib/Transform/ForwardOpTree.cpp +++ b/polly/lib/Transform/ForwardOpTree.cpp @@ -767,10 +767,6 @@ public: /// 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 diff --git a/polly/test/ForwardOpTree/forward_from_region.ll b/polly/test/ForwardOpTree/forward_from_region.ll new file mode 100644 index 00000000000..351758cffe9 --- /dev/null +++ b/polly/test/ForwardOpTree/forward_from_region.ll @@ -0,0 +1,78 @@ +; 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: } + diff --git a/polly/test/ForwardOpTree/forward_into_region.ll b/polly/test/ForwardOpTree/forward_into_region.ll new file mode 100644 index 00000000000..a79f1e4384c --- /dev/null +++ b/polly/test/ForwardOpTree/forward_into_region.ll @@ -0,0 +1,72 @@ +; 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: } diff --git a/polly/test/ForwardOpTree/noforward_region.ll b/polly/test/ForwardOpTree/noforward_from_region.ll index b32aef3dbeb..9994b82ef0e 100644 --- a/polly/test/ForwardOpTree/noforward_region.ll +++ b/polly/test/ForwardOpTree/noforward_from_region.ll @@ -1,14 +1,19 @@ ; RUN: opt %loadPolly -polly-optree -analyze < %s | FileCheck %s -match-full-lines ; -; Do not move instructions to region statements. +; 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 = 21.0 + 21.0; +; double val = A[0]; +; if (cond) ; -; bodyB_entry: -; if (undef) -; body_true: +; bodyA_true: +; A[0] = 42; +; +; bodyB: ; A[0] = val; ; } ; @@ -22,14 +27,15 @@ for: br i1 %j.cmp, label %bodyA, label %exit bodyA: - %val = fadd double 21.0, 21.0 + %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: - %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 @@ -47,5 +53,4 @@ return: ret void } - ; CHECK: ForwardOpTree executed, but did not modify anything |
