From 436db620e77366a9d9221cce35f7cd07582c57ad Mon Sep 17 00:00:00 2001 From: Michael Kruse Date: Tue, 26 Jan 2016 13:33:10 +0000 Subject: [PATCH] Unique value write accesses Ensure there is at most one write access per definition of an llvm::Value. Keep track of already created value write access by using a (dense) map. Replace addValueWriteAccess by ensureValueStore which can be uses more liberally without worrying to add redundant accesses. It will be used, e.g. in a logical correspondant for value reads -- ensureValueReload -- to ensure that the expected definition has been written when loading it. Differential Revision: http://reviews.llvm.org/D15483 llvm-svn: 258807 --- polly/include/polly/ScopInfo.h | 19 ++++++++++++++++--- polly/lib/Analysis/ScopInfo.cpp | 22 +++++++++++++++++++--- polly/test/ScopInfo/phi_scalar_simple_1.ll | 2 -- polly/test/ScopInfo/phi_scalar_simple_2.ll | 6 ------ 4 files changed, 35 insertions(+), 14 deletions(-) diff --git a/polly/include/polly/ScopInfo.h b/polly/include/polly/ScopInfo.h index 16d4d7e7..ae99631 100644 --- a/polly/include/polly/ScopInfo.h +++ b/polly/include/polly/ScopInfo.h @@ -830,6 +830,10 @@ private: /// @brief Mapping from instructions to (scalar) memory accesses. DenseMap InstructionToAccess; + /// @brief The set of values defined in this ScopStmt that are required + /// elsewhere, mapped to their MK_Value WRITE MemoryAccesses. + DenseMap ValueWrites; + //@} /// @brief A SCoP statement represents either a basic block (affine/precise @@ -993,6 +997,15 @@ public: return *ArrayAccess; } + /// @brief Return the MemoryAccess that writes the value of an instruction + /// defined in this statement, or nullptr if not existing, respectively + /// not yet added. + MemoryAccess *lookupValueWriteOf(Instruction *Inst) const { + assert((isRegionStmt() && R->contains(Inst)) || + (!isRegionStmt() && Inst->getParent() == BB)); + return ValueWrites.lookup(Inst); + } + void setBasicBlock(BasicBlock *Block) { // TODO: Handle the case where the statement is a region statement, thus // the entry block was split and needs to be changed in the region R. @@ -1917,7 +1930,7 @@ class ScopInfo : public RegionPass { /// @param Value The value to be written. /// @see addValueReadAccess() /// @see ScopArrayInfo::MemoryKind - void addValueWriteAccess(Instruction *Value); + void ensureValueWrite(Instruction *Value); /// @brief Create a MemoryAccess for reloading an llvm::Value. /// @@ -1925,7 +1938,7 @@ class ScopInfo : public RegionPass { /// /// @param Value The scalar expected to be loaded. /// @param User User of the scalar; this is where the access is added. - /// @see addValueWriteAccess() + /// @see ensureValueWrite() /// @see ScopArrayInfo::MemoryKind void addValueReadAccess(Value *Value, Instruction *User); @@ -1939,7 +1952,7 @@ class ScopInfo : public RegionPass { /// @param User The PHI node referencing @p Value. /// @param UserBB Incoming block for the incoming @p Value. /// @see addPHIWriteAccess() - /// @see addValueWriteAccess() + /// @see ensureValueWrite() /// @see ScopArrayInfo::MemoryKind void addValueReadAccess(Value *Value, PHINode *User, BasicBlock *UserBB); diff --git a/polly/lib/Analysis/ScopInfo.cpp b/polly/lib/Analysis/ScopInfo.cpp index 00055a0..4be9222 100644 --- a/polly/lib/Analysis/ScopInfo.cpp +++ b/polly/lib/Analysis/ScopInfo.cpp @@ -905,6 +905,12 @@ void ScopStmt::addAccess(MemoryAccess *Access) { if (Access->isArrayKind()) { MemoryAccessList &MAL = InstructionToAccess[AccessInst]; MAL.emplace_front(Access); + } else if (Access->isValueKind() && Access->isWrite()) { + Instruction *AccessVal = cast(Access->getAccessValue()); + assert(Parent.getStmtForBasicBlock(AccessVal->getParent()) == this); + assert(!ValueWrites.lookup(AccessVal)); + + ValueWrites[AccessVal] = Access; } MemAccs.push_back(Access); @@ -3554,7 +3560,7 @@ void ScopInfo::buildPHIAccesses(PHINode *PHI, Region &R, if (scop->getStmtForBasicBlock(OpIBB) != scop->getStmtForBasicBlock(OpBB)) { addValueReadAccess(OpI, PHI, OpBB); - addValueWriteAccess(OpI); + ensureValueWrite(OpI); } } else if (ModelReadOnlyScalars && !isa(Op)) { addValueReadAccess(Op, PHI, OpBB); @@ -3873,7 +3879,7 @@ void ScopInfo::buildAccessFunctions(Region &R, BasicBlock &BB, if (buildScalarDependences(Inst, &R, NonAffineSubRegion)) { if (!isa(Inst)) - addValueWriteAccess(Inst); + ensureValueWrite(Inst); } } } @@ -3931,7 +3937,17 @@ void ScopInfo::addArrayAccess(Instruction *MemAccInst, ElemBytes, IsAffine, AccessValue, Subscripts, Sizes, ScopArrayInfo::MK_Array); } -void ScopInfo::addValueWriteAccess(Instruction *Value) { +void ScopInfo::ensureValueWrite(Instruction *Value) { + ScopStmt *Stmt = scop->getStmtForBasicBlock(Value->getParent()); + + // Value not defined within this SCoP. + if (!Stmt) + return; + + // Do not process further if the value is already written. + if (Stmt->lookupValueWriteOf(Value)) + return; + addMemoryAccess(Value->getParent(), Value, MemoryAccess::MUST_WRITE, Value, 1, true, Value, ArrayRef(), ArrayRef(), ScopArrayInfo::MK_Value); diff --git a/polly/test/ScopInfo/phi_scalar_simple_1.ll b/polly/test/ScopInfo/phi_scalar_simple_1.ll index 0d13a21..170421b 100644 --- a/polly/test/ScopInfo/phi_scalar_simple_1.ll +++ b/polly/test/ScopInfo/phi_scalar_simple_1.ll @@ -24,8 +24,6 @@ ; CHECK-NEXT: [N] -> { Stmt_for_cond[i0] -> MemRef_x_addr_0__phi[] }; ; CHECK-NEXT: MustWriteAccess := [Reduction Type: NONE] [Scalar: 1] ; CHECK-NEXT: [N] -> { Stmt_for_cond[i0] -> MemRef_x_addr_0[] }; -; CHECK-NEXT: MustWriteAccess := [Reduction Type: NONE] [Scalar: 1] -; CHECK-NEXT: [N] -> { Stmt_for_cond[i0] -> MemRef_x_addr_0[] }; ; CHECK-NEXT: Stmt_for_body ; CHECK-NEXT: Domain := ; CHECK-NEXT: [N] -> { Stmt_for_body[i0] : N >= 2 and 0 <= i0 <= -2 + N }; diff --git a/polly/test/ScopInfo/phi_scalar_simple_2.ll b/polly/test/ScopInfo/phi_scalar_simple_2.ll index e4445df..89eaa2c 100644 --- a/polly/test/ScopInfo/phi_scalar_simple_2.ll +++ b/polly/test/ScopInfo/phi_scalar_simple_2.ll @@ -20,8 +20,6 @@ ; CHECK-NEXT: [N, c] -> { Stmt_for_cond[i0] -> MemRef_x_addr_0[] }; ; CHECK-NEXT: MustWriteAccess := [Reduction Type: NONE] [Scalar: 0] ; CHECK-NEXT: [N, c] -> { Stmt_for_cond[i0] -> MemRef_A[i0] }; -; CHECK-NEXT: MustWriteAccess := [Reduction Type: NONE] [Scalar: 1] -; CHECK-NEXT: [N, c] -> { Stmt_for_cond[i0] -> MemRef_x_addr_0[] }; ; CHECK-NEXT: Stmt_for_body ; CHECK-NEXT: Domain := ; CHECK-NEXT: [N, c] -> { Stmt_for_body[i0] : 0 <= i0 < N }; @@ -40,10 +38,6 @@ ; CHECK-NEXT: [N, c] -> { Stmt_for_cond1[i0, i1] -> MemRef_x_addr_1[] }; ; CHECK-NEXT: ReadAccess := [Reduction Type: NONE] [Scalar: 1] ; CHECK-NEXT: [N, c] -> { Stmt_for_cond1[i0, i1] -> MemRef_x_addr_1__phi[] }; -; CHECK-NEXT: MustWriteAccess := [Reduction Type: NONE] [Scalar: 1] -; CHECK-NEXT: [N, c] -> { Stmt_for_cond1[i0, i1] -> MemRef_x_addr_1[] }; -; CHECK-NEXT: MustWriteAccess := [Reduction Type: NONE] [Scalar: 1] -; CHECK-NEXT: [N, c] -> { Stmt_for_cond1[i0, i1] -> MemRef_x_addr_1[] }; ; CHECK-NEXT: Stmt_for_body3 ; CHECK-NEXT: Domain := ; CHECK-NEXT: [N, c] -> { Stmt_for_body3[i0, i1] : 0 <= i0 < N and 0 <= i1 < N }; -- 2.7.4