Index: lib/Transform/ForwardOpTree.cpp =================================================================== --- lib/Transform/ForwardOpTree.cpp +++ lib/Transform/ForwardOpTree.cpp @@ -386,6 +386,8 @@ /// @param DefToTarget { DomainDef[] -> DomainTarget[] } /// A mapping from the statement instance @p Inst is /// defined to the statement instance it is forwarded to. + /// @param MovedInsts A set in which the newly added instructions will be + /// recorded. /// @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 @@ -397,11 +399,11 @@ /// instance. /// FD_CanForwardTree if @p Inst is forwardable. /// FD_DidForward if @p DoIt was true. - ForwardingDecision forwardKnownLoad(ScopStmt *TargetStmt, Instruction *Inst, - ScopStmt *UseStmt, Loop *UseLoop, - isl::map UseToTarget, ScopStmt *DefStmt, - Loop *DefLoop, isl::map DefToTarget, - bool DoIt) { + ForwardingDecision + forwardKnownLoad(ScopStmt *TargetStmt, Instruction *Inst, ScopStmt *UseStmt, + Loop *UseLoop, isl::map UseToTarget, ScopStmt *DefStmt, + Loop *DefLoop, isl::map DefToTarget, + SmallVectorImpl &MovedInsts, bool DoIt) { // Cannot do anything without successful known analysis. if (Known.is_null()) return FD_NotApplicable; @@ -422,12 +424,14 @@ if (Access && !DoIt) return FD_CanForwardLeaf; - if (DoIt) + if (DoIt) { TargetStmt->prependInstruction(LI); + MovedInsts.push_back(LI); + } ForwardingDecision OpDecision = forwardTree(TargetStmt, LI->getPointerOperand(), DefStmt, DefLoop, - DefToTarget, DoIt); + DefToTarget, MovedInsts, DoIt); switch (OpDecision) { case FD_CannotForward: assert(!DoIt); @@ -528,6 +532,8 @@ /// @param DefToTarget { DomainDef[] -> DomainTarget[] } /// A mapping from the statement instance @p UseInst is /// defined to the statement instance it is forwarded to. + /// @param MovedInsts A set in which the newly added instructions will be + /// recorded. /// @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 @@ -538,10 +544,10 @@ /// forwardable. /// FD_CanForwardTree if @p UseInst is forwardable. /// FD_DidForward if @p DoIt was true. - ForwardingDecision forwardSpeculatable(ScopStmt *TargetStmt, - Instruction *UseInst, - ScopStmt *DefStmt, Loop *DefLoop, - isl::map DefToTarget, bool DoIt) { + ForwardingDecision + forwardSpeculatable(ScopStmt *TargetStmt, Instruction *UseInst, + ScopStmt *DefStmt, Loop *DefLoop, isl::map DefToTarget, + SmallVectorImpl &MovedInsts, bool DoIt) { // PHIs, unless synthesizable, are not yet supported. if (isa(UseInst)) return FD_NotApplicable; @@ -568,13 +574,14 @@ // TODO: The operand tree is not really a tree, but a DAG. We should be // able to handle DAGs without duplication. TargetStmt->prependInstruction(UseInst); + MovedInsts.push_back(UseInst); NumInstructionsCopied++; TotalInstructionsCopied++; } for (Value *OpVal : UseInst->operand_values()) { - ForwardingDecision OpDecision = - forwardTree(TargetStmt, OpVal, DefStmt, DefLoop, DefToTarget, DoIt); + ForwardingDecision OpDecision = forwardTree( + TargetStmt, OpVal, DefStmt, DefLoop, DefToTarget, MovedInsts, DoIt); switch (OpDecision) { case FD_CannotForward: assert(!DoIt); @@ -610,6 +617,8 @@ /// @param UseToTarget { DomainUse[] -> DomainTarget[] } /// A mapping from the statement instance @p UseVal is used /// to the statement instance it is forwarded to. + /// @param MovedInsts A set in which the newly added instructions will be + /// recorded. /// @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 @@ -619,7 +628,9 @@ /// If DoIt==true, return FD_DidForward. ForwardingDecision forwardTree(ScopStmt *TargetStmt, Value *UseVal, ScopStmt *UseStmt, Loop *UseLoop, - isl::map UseToTarget, bool DoIt) { + isl::map UseToTarget, + SmallVectorImpl &MovedInsts, + bool DoIt) { ScopStmt *DefStmt = nullptr; Loop *DefLoop = nullptr; @@ -710,13 +721,13 @@ } ForwardingDecision SpeculativeResult = forwardSpeculatable( - TargetStmt, Inst, DefStmt, DefLoop, DefToTarget, DoIt); + TargetStmt, Inst, DefStmt, DefLoop, DefToTarget, MovedInsts, DoIt); if (SpeculativeResult != FD_NotApplicable) return SpeculativeResult; ForwardingDecision KnownResult = forwardKnownLoad(TargetStmt, Inst, UseStmt, UseLoop, UseToTarget, - DefStmt, DefLoop, DefToTarget, DoIt); + DefStmt, DefLoop, DefToTarget, MovedInsts, DoIt); if (KnownResult != FD_NotApplicable) return KnownResult; @@ -730,7 +741,8 @@ } /// Try to forward an operand tree rooted in @p RA. - bool tryForwardTree(MemoryAccess *RA) { + bool tryForwardTree(MemoryAccess *RA, + SmallVectorImpl &MovedInsts) { assert(RA->isLatestScalarKind()); DEBUG(dbgs() << "Trying to forward operand tree " << RA << "...\n"); @@ -744,19 +756,19 @@ isl::map::identity(DomSpace.map_from_domain_and_range(DomSpace)); } - ForwardingDecision Assessment = forwardTree( - Stmt, RA->getAccessValue(), Stmt, InLoop, TargetToUse, false); + ForwardingDecision Assessment = + forwardTree(Stmt, RA->getAccessValue(), Stmt, InLoop, TargetToUse, + MovedInsts, false); assert(Assessment != FD_DidForward); if (Assessment != FD_CanForwardTree) return false; - ForwardingDecision Execution = forwardTree(Stmt, RA->getAccessValue(), Stmt, - InLoop, TargetToUse, true); + ForwardingDecision Execution = + forwardTree(Stmt, RA->getAccessValue(), Stmt, InLoop, TargetToUse, + MovedInsts, true); assert(Execution == FD_DidForward && "A previous positive assessment must also be executable"); (void)Execution; - - Stmt->removeSingleMemoryAccess(RA); return true; } @@ -781,8 +793,10 @@ Accs.push_back(RA); } + SmallVector MovedInsts; + for (MemoryAccess *RA : Accs) { - if (tryForwardTree(RA)) { + if (tryForwardTree(RA, MovedInsts)) { Modified = true; StmtModified = true; NumForwardedTrees++; @@ -790,6 +804,12 @@ } } + for (Instruction *Inst : MovedInsts) { + MemoryAccess *MA = Stmt.lookupInputAccessOf(Inst); + if (MA) + Stmt.removeSingleMemoryAccess(MA); + } + if (StmtModified) { NumModifiedStmts++; TotalModifiedStmts++; Index: test/ForwardOpTree/forward_into_region_redundant_use.ll =================================================================== --- /dev/null +++ test/ForwardOpTree/forward_into_region_redundant_use.ll @@ -0,0 +1,56 @@ +; RUN: opt %loadPolly -polly-invariant-load-hoisting=true -polly-optree -analyze < %s | FileCheck %s -match-full-lines +; + +define void @foo(float* %A, i32 %p, float* %B) { +start: + br label %branch + +branch: + %cmp = icmp eq i32 %p, 1024 + br i1 %cmp, label %next, label %end + +next: + %val = load float, float* %A + %fcmp = fcmp oeq float %val, 41.0 + br label %nonaffine + +nonaffine: + br i1 %fcmp, label %a, label %b + +a: + store float %val, float* %A + br label %end + +b: + store float 1.0, float* %A + br label %end + +end: + ret void +} + +; CHECK: After statements { +; CHECK-NEXT: Stmt_next +; CHECK-NEXT: ReadAccess := [Reduction Type: NONE] [Scalar: 0] +; CHECK-NEXT: [p] -> { Stmt_next[] -> MemRef_A[0] }; +; CHECK-NEXT: MustWriteAccess := [Reduction Type: NONE] [Scalar: 1] +; CHECK-NEXT: [p] -> { Stmt_next[] -> MemRef_fcmp[] }; +; CHECK-NEXT: MustWriteAccess := [Reduction Type: NONE] [Scalar: 1] +; CHECK-NEXT: [p] -> { Stmt_next[] -> MemRef_val[] }; +; CHECK-NEXT: Instructions { +; CHECK-NEXT: %val = load float, float* %A +; CHECK-NEXT: %fcmp = fcmp oeq float %val, 4.100000e+01 +; CHECK-NEXT: } +; CHECK-NEXT: Stmt_nonaffine__TO__end +; CHECK-NEXT: ReadAccess := [Reduction Type: NONE] [Scalar: 0] +; CHECK-NEXT: null; +; CHECK-NEXT: new: [p] -> { Stmt_nonaffine__TO__end[] -> MemRef_A[0] }; +; CHECK-NEXT: MayWriteAccess := [Reduction Type: NONE] [Scalar: 0] +; CHECK-NEXT: [p] -> { Stmt_nonaffine__TO__end[] -> MemRef_A[0] }; +; CHECK-NEXT: MayWriteAccess := [Reduction Type: NONE] [Scalar: 0] +; CHECK-NEXT: [p] -> { Stmt_nonaffine__TO__end[] -> MemRef_A[0] }; +; CHECK-NEXT: Instructions { +; CHECK-NEXT: %val = load float, float* %A +; CHECK-NEXT: %fcmp = fcmp oeq float %val, 4.100000e+01 +; CHECK-NEXT: } +; CHECK-NEXT: } Index: test/ForwardOpTree/forward_load_tripleuse.ll =================================================================== --- test/ForwardOpTree/forward_load_tripleuse.ll +++ test/ForwardOpTree/forward_load_tripleuse.ll @@ -150,8 +150,6 @@ ; CHECK-NEXT: [n] -> { Stmt_bodyB[i0] -> MemRef_B[i0] }; ; CHECK-NEXT: MustWriteAccess := [Reduction Type: NONE] [Scalar: 0] ; CHECK-NEXT: [n] -> { Stmt_bodyB[i0] -> MemRef_C[i0] }; -; CHECK-NEXT: ReadAccess := [Reduction Type: NONE] [Scalar: 1] -; CHECK-NEXT: [n] -> { Stmt_bodyB[i0] -> MemRef_val1[] }; ; CHECK-NEXT: Instructions { ; CHECK-NEXT: %val1 = load double, double* %A_idx ; CHECK-NEXT: %val1 = load double, double* %A_idx