Index: polly/trunk/include/polly/ScopInfo.h =================================================================== --- polly/trunk/include/polly/ScopInfo.h +++ polly/trunk/include/polly/ScopInfo.h @@ -1601,7 +1601,6 @@ /// 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); } Index: polly/trunk/lib/Support/VirtualInstruction.cpp =================================================================== --- polly/trunk/lib/Support/VirtualInstruction.cpp +++ polly/trunk/lib/Support/VirtualInstruction.cpp @@ -180,12 +180,16 @@ static void addInstructionRoots(ScopStmt *Stmt, SmallVectorImpl &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; } Index: polly/trunk/lib/Transform/ForwardOpTree.cpp =================================================================== --- polly/trunk/lib/Transform/ForwardOpTree.cpp +++ polly/trunk/lib/Transform/ForwardOpTree.cpp @@ -767,10 +767,6 @@ /// 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 Index: polly/trunk/test/ForwardOpTree/forward_from_region.ll =================================================================== --- polly/trunk/test/ForwardOpTree/forward_from_region.ll +++ polly/trunk/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: } + Index: polly/trunk/test/ForwardOpTree/forward_into_region.ll =================================================================== --- polly/trunk/test/ForwardOpTree/forward_into_region.ll +++ polly/trunk/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: } Index: polly/trunk/test/ForwardOpTree/noforward_from_region.ll =================================================================== --- polly/trunk/test/ForwardOpTree/noforward_from_region.ll +++ polly/trunk/test/ForwardOpTree/noforward_from_region.ll @@ -0,0 +1,56 @@ +; 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 Index: polly/trunk/test/ForwardOpTree/noforward_region.ll =================================================================== --- polly/trunk/test/ForwardOpTree/noforward_region.ll +++ polly/trunk/test/ForwardOpTree/noforward_region.ll @@ -1,51 +0,0 @@ -; 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