Index: include/polly/ScopInfo.h =================================================================== --- include/polly/ScopInfo.h +++ 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); } @@ -1927,9 +1926,6 @@ Scop(Region &R, ScalarEvolution &SE, LoopInfo &LI, ScopDetection::DetectionContext &DC, OptimizationRemarkEmitter &ORE); - /// Return the LoopInfo used for this Scop. - LoopInfo *getLI() const { return Affinator.getLI(); } - //@} /// Initialize this ScopBuilder. @@ -2370,6 +2366,9 @@ Scop &operator=(const Scop &) = delete; ~Scop(); + /// Return the LoopInfo used for this Scop. + LoopInfo *getLI() const { return Affinator.getLI(); } + /// Get the count of copy statements added to this Scop. /// /// @return The count of copy statements added to this Scop. Index: lib/Support/VirtualInstruction.cpp =================================================================== --- lib/Support/VirtualInstruction.cpp +++ lib/Support/VirtualInstruction.cpp @@ -183,9 +183,12 @@ // 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); + for (Instruction *Inst : Stmt->getInstructions()) + RootInsts.emplace_back(Stmt, Inst); + for (BasicBlock *BB : Stmt->getRegion()->blocks()) + if (Stmt->getRegion()->getEntry() != BB) + for (Instruction &Inst : *BB) + RootInsts.emplace_back(Stmt, &Inst); return; } Index: lib/Transform/ForwardOpTree.cpp =================================================================== --- lib/Transform/ForwardOpTree.cpp +++ 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: test/ForwardOpTree/forward_from_region.ll =================================================================== --- /dev/null +++ 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-NEXT: Instructions copied: 1 +; CHECK-NEXT: Known loads forwarded: 0 +; CHECK-NEXT: Read-only accesses copied: 0 +; CHECK-NEXT: Operand trees forwarded: 1 +; CHECK-NEXT: Statements with forwarded operand trees: 1 +; CHECK-NEXT: } +; CHECK-NEXT: After statements { +; CHECK-NEXT: Stmt_bodyA__TO__bodyB +; CHECK-NEXT: MayWriteAccess := [Reduction Type: NONE] [Scalar: 0] +; CHECK-NEXT: [n] -> { Stmt_bodyA__TO__bodyB[i0] -> MemRef_A[0] }; +; CHECK-NEXT: MustWriteAccess := [Reduction Type: NONE] [Scalar: 1] +; CHECK-NEXT: [n] -> { Stmt_bodyA__TO__bodyB[i0] -> MemRef_val[] }; +; 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: 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: } + Index: test/ForwardOpTree/forward_into_region.ll =================================================================== --- /dev/null +++ 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: test/ForwardOpTree/noforward_from_region.ll =================================================================== --- test/ForwardOpTree/noforward_from_region.ll +++ test/ForwardOpTree/noforward_from_region.ll @@ -1,18 +1,20 @@ ; RUN: opt %loadPolly -polly-optree -analyze < %s | FileCheck %s -match-full-lines ; -; Do not move instructions to region statements. +; Move instructions from region statements. ; ; for (int j = 0; j < n; j += 1) { ; bodyA: ; double val = 21.0 + 21.0; +; if (cond) ; -; bodyB_entry: -; if (undef) -; body_true: +; bodyA_true: +; A[0] = 42; +; +; bodyB: ; A[0] = val; ; } ; -define void @func(i32 %n, double* noalias nonnull %A) { +define void @func(i32 %n, double* noalias nonnull %A, double* noalias nonnull %B) { entry: br label %for @@ -22,14 +24,16 @@ 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: + %x = load double, double* %A + store double %x, 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 +51,4 @@ ret void } - ; CHECK: ForwardOpTree executed, but did not modify anything